Two Machines

Interview

Time limit0.5sMemory limit512 MB

Summary

Assign each of n tasks to machine A or B, minimizing the maximum total load across the two machines.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Sorting, Binary search
Solved: No attempts yet

Problem

The scheduling optimization company SOPT has n tasks t1, t2, ..., tn that must be completed. SOPT owns two machines, A and B. To complete each task ti, SOPT can choose exactly one of machine A and machine B. If machine A is chosen to complete task ti, it takes ai time; if machine B is chosen, it takes bi time. Each machine can perform at most one task at any moment, and once a task starts, no other task can be performed on that machine until the task finishes. SOPT wants to find the minimum completion time for finishing all tasks.

For example, suppose three tasks t1, t2, t3 are given with a1 = 2, b1 = 3, a2 = 5, b2 = 3, a3 = 2, b3 = 7. To minimize the completion time, assign tasks t1 and t3 to machine A, and task t2 to machine B. Machine A takes 2 + 2 = 4 time to complete tasks t1 and t3, and machine B takes 3 time to complete task t2. Thus the minimum completion time is 4. Given n tasks t1, t2, ..., tn and the times each machine takes to perform each task, write a program that finds the minimum time required to complete all tasks.

Input

Input comes from standard input. The first line contains a positive integer n (1 ≤ n ≤ 250), the number of tasks. In the following n lines, the i-th line contains two integers ai, bi (1 ≤ ai, bi ≤ 250). Here ai and bi are the times required to complete task ti on machines A and B, respectively.

Output

Output goes to standard output. Print the minimum completion time for completing all tasks t1, t2, ..., tn on one line.

Examples2

Example 1
Input
```
3
2 3
5 3
2 7
```
Expected output
```
4
```
Example 2
Input
```
3
9 2
10 4
5 2
```
Expected output
```
6
```