Kelvin and Tomato are the TAs of ACM class 2010
Being responsible for each week's homework, they've decided to divide their work: Tomato sets the problems, and Kelvin will generate testcases and write alternate solutions.
(in the start Kelvin proposed that he plays dota and Tomato does all the works but Tomato kindly refused.)
Of course, Kelvin's part of work (ex: testcase generation) of a particular problem can only between after Tomato sets that particular problem; that is, Kelvin will have to wait until Tomato finish his job until he can start his work on that problem.
Now they are to set a total of N problems, each problem is described by a pair of numbers Ti, Ki indicating that Tomato's part of job requires time Ti, Kelvin's part requires time Ki. Given these information, what is the least amount of time they'd need to finish all their jobs?
On the fisrt line an integer T indicated the number of testcases.
Each testcase starts with a single integer N, the number of problems in the homework assignment. The next N line each contains two integers: Ti and Ki.
For each test case, print the minimum time required to complete the whole problemsetting process.
2 3 8 1 1 6 6 3 3 4 1 5 1 6 6
16 16
Migrated from old NTUJ.
uva11269
| No. | Testdata Range | Score |
|---|