Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
FlashGet
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 2949Accepted: 493

Description

You are downloading 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 max speed. When a task is over, the bandwidth used is distributed 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.

Input

There are multiple cases in the input.

The first line of each case contains 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 initial speed and the max speed. The input promises the sum of tasks' speed equals to the total bandwidth, the speed is not higher than the max speed.

The input is terminated by a zero.

Output

For each case first print "Case %:" in one line, % is the number of cases.
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

0

Sample Output

Case 1:
NO1:5.000s
NO2:6.667s
NO3:12.500s

Hint

The bandwidth will never change if no task is finished.

When a task finished, the bandwidth is distributed by this rule:
Every unfinished task which does not reach the max speed gets the same bandwidth; the total bandwidth can not be overflowed; every task's speed can not overflow its max speed; if there is bandwidth can be used, distribute it.

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator