Problem2873--突击战[Commando War,UVa11729]

2873: 突击战[Commando War,UVa11729]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Status] [Submit] [Creator:]

Description

你有N个部下,每个部下需要独立完成一项任务。第i个部下需要你花费Bi分钟交代任务,然后他会立刻独立、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序,使得所有任务尽早执行完毕(即最后一个执行完的任务应尽早结束)。
注意,不能同时给两个部下交代任务,但部下们可以同时执行他们各自的任务。

Input

输入包含多组数据。
每组数据的第一行为部下的个数N,(1≤N≤1000)
接下来N行,每行两个用空格隔开的正整数B和J,分别代表第i个部下交代任务花费的时间Bi和执行任务的时间Ji.(1≤B,J≤10000)
当输入为单独的一行“0”时,表示输入结束

Output

对于每组数据,输出所有任务完成的最短时间。输出格式为’Case X: Y‘。X是数据编号,Y是所有任务完成的最短时间。

Sample Input Copy

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

Sample Output Copy

Case 1: 8
Case 2: 15

Source/Category