
90  The 7th Zhejiang Provincial Collegiate Programming Contest  J
There are two machines A and B. There are n tasks, namely task 1, task 2, ..., task n. You must assign each task to one machine to process it. There are some facts you must know and comply with:
You want to do finish all the tasks as soon as possible. Input There are multiple test cases. The first line of the input is an integer T (0 < T < 1000) indicating the number of test cases. Then T test cases follow. Each test case starts with an integer n (0 < n < 100). The ith line of the next n lines contains two integers tA, tB (0 < tA, tB < 100), giving the time to process the ith task by machine A and machine B. Output For each test case, output the earliest time when all the tasks have been processed. Sample Input 4 1 1 2 2 1 2 2 1 2 1 2 90 95 3 1 3 1 3 1 3 Sample Output 1 1 90 3 Hints
Author: CAO, Peng Source: The 7th Zhejiang Provincial Collegiate Programming Contest 