Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2847

Time Limit: 2 Seconds      Memory Limit: 65536 KB

You are download some things using a software (Flashget, maybe),but suddenly you have to go away for something. So, you need a program to calculate when the tasks will complete.

Now you know every download's speed��size and the max speed. When a task is over, the bandwidth he used is distribute by other tasks. The speed of one task can never go beyond the max speed of this task, and all tasks' speed can never be larger than the total bandwidth.


The are multiple cases in the input.

The first line of one case is two integers, n and t.n<=100.n is the number of tasks, and t is the total bandwidth. There follows n lines , one line has three integers ,means the size of the download file, the initialize speed and the max speed. The input promises the sum of tasks' speed equals to the total bandwidth, the speed is not larger than the max speed.

The input is terminate by a zero.


For each case first print "Case %:" in one line,% is the number of case.

Then print n lines for n tasks, like this:

NO*:#s * means the number of task, for the sequence of input;# means the finish time of the task.

Sample Input

3 65
100 20 30
200 30 30
300 15 30


Sample Output

Case 1:


The bindwidth will never change if no task is finish.
When a task finished, the bindwidth is distributed follow this rule:
Every unfinished task which is not reach the max speed gets the same bindwidth;the total bandwidth can not be overflowed; every task's speed can not overflow its max speed; if there are bindwidth can be used, distribute it.

Author: Jia Li, zzningxp
Source: South Central China 2007 hosted by NUDT
Submit    Status