Commando War

题意翻译

# 突击战 你有n个部下,每个部下需要完成一项任务。第i个部下需要你花Bj分钟交代任务,然后他就会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序,使得所有任务尽早执行完毕(即最后一个执行完的任务应尽早结束)。注意,不能同时给两个部下交代任务,但部下们可以同时执行他们各自的任务。 #### 输入格式 输入包含多组数据,每组数据的第一行为部下的个数N(1<=N<=1000);以下N行每行两个正整数B和J(1<=B<=10000,1<=J<=10000),即交待任务的时间和执行任务的时间。输入结束标志为N=0。 #### 输出格式 对于每组数据,输出所有任务完成的最短时间。 ### 样例输入 3 2 5 3 2 2 1 3 3 3 4 4 5 5 0 ### 样例输出 Case 1:8 Case 2:15 由 @Legends丶dream 提供翻译

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2829 [PDF](https://uva.onlinejudge.org/external/117/p11729.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11729/a5e31e5ee0ec61f4f6f02b7737e2e4ce2c5e7c38.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11729/6e91e17ae73c44a7f45c72d0d1620df0c2cabe0a.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11729/e60554938646162e3b157d4913318721be8f64e7.png)

输入输出样例

输入样例 #1

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

输出样例 #1

Case 1: 8
Case 2: 15