问题 2066. -- 突击战

2066: 突击战

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

题目描述

或许每个人都有成为将军的梦想,小光也是如此。从小,小光就立志长大了以后要做一名军人,保家卫国。有一天,他做了一个梦,在梦里,他是一个英明神武的将军,但是敌国马上就要入侵了,作为将军的他责无旁贷需要挺身而出,于是他开始做一些战略部署。
假设当前小光有n个部下,每个部下需要完成一项任务。第i个部下需要小光花Bi分钟交代任务,然后他会立刻独立地、无间断地执行Ji分钟后完成任务。小光需要选择交代任务的顺序,使得所有任务尽早执行完毕(即最后一个执行完的任务应尽早结束)。注意,不能同时给两个部下交代任务,但部下们可以同时执行他们各自的任务。 

输入

第一行为部下的个数n(1<=n<=1000);
接下来n行,每行两个正整数B和J(1<=B<=10000,1<=J<=10000),即交待任务的时间和执行任务的时间。

输出

输出所有任务完成的最短时间。

样例输入

3
2 5
3 2
2 1

样例输出

8

提示

样例2:
输入:
3
3 3
4 4
5 5
输出: 15

来源

[提交][状态]