[Commando War,Uva 11729]突击战

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file commando.in Output file commando.out

【题目描述】

你有n个部下,每个部下需要完成一项任务。第i个部下需要你花Bi分钟交代任务,然后他会立刻独立地,无间断的执行Ji分钟后完成任务。你需要交代任务的顺序,使得所有的任务尽早执行完毕。注意,不能同时给2个部下交代任务,但是部下可以同时执行各自的任务。

【输入格式】

输入数据包括多组数据,每组数据的第一行为部下的个数N(1≤N≤1000);以下N行有2个正整数B和J(1≤B≤1000,1≤J≤1000),即交代任务的时间和执行任务的时间。输入结束标志符为N=0。

【输出格式】commando.in

对于每组数据,输出(以第i组数据为例):

Case i: Time

【样例输入】commando.out

3
2 5
3 2
2 1
3
3 3
4 4
5 5
0

【样例输出】

Case 1: 8
Case 2: 15

【来源】

From UVa 11729.