#OJ1209. Time Limit: 1 Sec Memory Limit: 128 MB
Time Limit: 1 Sec Memory Limit: 128 MB
Time Limit: 1 Sec Memory Limit: 128 MB
Description
你有N个部下,每个部下需要完成一项任务。第i个部下需要你花Bi分钟交代任务,然后他会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交待人物的顺序,使得所有任务尽早执行完毕(即最后一个执行的任务应尽早结束)。 注意,不能同时给两个部下交待任务,但部下们可以同时执行他们各自的任务。
Input
输入中第一行为T,即case数。 每个case第一行为部下的个数N(1 <= N <= 1000);以下N行每行两个正整数B和J(1 <= B <= 10000,1 <= J <= 10000,),即交待任务的时间和执行任务的时间。
Output
输出所有任务完成的最短时间。
Sample Input
2
3
2 5
3 2
2 1
3
3 3
4 4
5 5
Sample Output
Case 1: 8
Case 2: 15
HINT
Append Code
Source