提示: 欢迎访问OurACM平台。
Problem 1226 分布式计算问题

Accept: 195    Submit: 572
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

福州大学计算机学院实验中心有一台高性能超级计算机。这台超级计算机可以连接任意多台高端PC。学院高性能计算研究小组的科学家们在进行一项复杂计算研究时,用分治策略将计算任务分解为n个互不相同的子任务J1,J2,…,Jn。每个子任务都需要2 个阶段来完成。首先,需要用超级计算机对每个子任务进行预处理,然后由超级计算机将子任务分配给高端PC去完成。超级计算机对子任务i的预处理时间为Pi,而在高端PC 完成子任务i的时间为fi。超级计算机只能以串行的方式对n 个子任务J1,J2,…,Jn进行预处理,一旦交给高端PC 后,所有高端PC 可以并行地进行计算。分布式计算问题要求确定超级计算机对n个子任务进行预处理的最优次序,使全部完成n个子任务的时间最早。

对于给定的n个互不相同的子任务J1,J2,…,Jn,以及超级计算机预处理各子任务的时间和高端PC完成各子任务的时间,计算全部完成n个子任务的最早时间。假设超级计算机开始预处理子任务的时间为0。

Input

第一行有1 个正整数n(1<n<2000000),表示有n个互不相同的子任务。

接下来的n行中每行有2 个正整数,分别表示超级计算机预处理相应的子任务所需的时间和高端PC完成该子任务所需的时间。

处理到文件末尾。

Output

最早完成的时间

Sample Input

5 65 3 57 8 13 6 37 8 80 3

Sample Output

255

Source

FJ CFCS 2007

Submit  Back  Status  Discuss