By Unknown Brazil
The Science Academy of Czech Republic, worried about the summer floods in Prague, is fostering the development of a new computational cluster, it has, among other tasks, to make a more accurate weather forecast. This new cluster is composed by m equally machines working in parallel. Because of budget reasons, each machine may process only a task at once, and each task can not be processed in more than one machine simultaneously. The cluster allows, however, pre-emption. In other words, it is possible to interrupt the execution of a task and return it posteriorly, in other machine if necessary.
You've been invited to an Computer Science related event to develop a preliminary version of task scheduler of the cluster, since you were in Prague. In this version, it's provided a set of tasks T, in which one task t ∈ T has:
Your scheduler must receive that data, accordingly with the format described below and it must tell if there is or not a viable scheduling, or in other words, a scheduling that completes every task in the time interval allowed.
Your scheduler must be prepared to work with various instances of input. Each instance follows this format. On the first line are provided the number of machines, 0 ≤ m ≤ 100, and tasks, 0 ≤ n ≤ 1000, respectively. On the next n lines are provided the values pt ≥ 0, rt ≥ 0 and dt ≥ 0 (one triple per line) for the tasks t ∈ T. The instants rt and dt are integers, and pt is decimal. Values m = 0 and n = 0 indicates that the instances processing is finished and there's nothing more to process. All the input values of the same line are separated by any number of empty spaces.
For each solved instance, you must print an identifier Instance h, in which h is an integer number, sequential and crescent starting from 1. On the next line it must be printed Viable or Not Viable, depending of the scheduling for the instance if it's viable or not, respectively. An empty line must separate each instance output.
|Sample Input||Sample Output|
1.5 3 5
1.25 1 3
2.1 3 7
3.6 5 9
3 1 2