问题 1005. -- 任务繁忙的ACM协会

1005: 任务繁忙的ACM协会

时间限制: 1 Sec  内存限制: 128 MB
提交: 277  解决: 77
[提交][状态][讨论版]

题目描述

最近要筹办ACM-ICPC亚洲区域赛,对于新疆大学软件学院ACM协会来说可是件大事,大大小小的事特别多。ACM协会由一个会长和很多部长组成,会长主要负责筹划和安排任务,具体任务由部长完成。我们已经知道了需要完成的任务有N项,以及知道了第i项任务的具体需要会长的交代时间Bi和部长的执行时间Ji。假设部长足够多,会长安排一个部长任务后,部长回立刻执行。现在需要你们帮会长确定一个合理的任务安排顺序,使得所有任务最早的执行完毕(即最后一个执行完成的任务尽量早的结束)。注意,会长不能同时给两个部长同时交代任务,但每个部长可以同时独立的执行给他们各自的任务。


输入

输入包含多组数据,每组数据的第一行为任务数N1<=N<=1000;以下N行每行有两个正整数BJ(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

提示

来源

[提交][状态]