Time Limit: Java: 1000 ms / Others: 1000 ms

Memory Limit: Java: 32768 KB / Others: 32768 KB

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 must assign each task to only one machine to process.
- At any time, a machine can process at most one task.
- Task i (0 < i < n) can be processed if and only if each task j (0 < j < i) has been processed or processing.
- If a task is processing on one machine, it cannot be interrupted.

You want to do finish all the tasks as soon as possible.

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.

提交代码