Description

After the morning training, the THU ACM team goes to have lunch. A group of $N$ people arrive at the famous Canteen No. 10. There are two serving windows, and each window can serve at most one person at a time. Because everyone has different tastes (and appetites), the time needed to be served varies by person. Everyone also eats at a different speed, so the eating time may also differ.

Their plan is: first split all people into two queues and decide the order within each queue. Then queue 1 lines up at window 1, and queue 2 at window 2. Each person starts eating immediately after being served. As soon as everyone finishes eating, they gather to go to the basement of Teaching Building No. 6 for the afternoon training.

Given the serving time and eating time of each person, arrange the teams and the order to make the time when everyone finishes eating as early as possible.

Assume the THU ACM team arrives at time $0$, and there are no other diners in the canteen (only the servers). Each person must be assigned to exactly one queue. The two windows operate in parallel and do not affect each other, and a person’s serving time is independent of the window. After being served, each person starts eating immediately with no delay.

Given the serving and eating times of $N$ people, output the time when everyone finishes eating under the optimal plan.

Input Format

The first line contains an integer $N$, the total number of people.

Each of the next $N$ lines contains two integers $A_i, B_i$, representing the $i$-th person’s serving time and eating time.

Output Format

A single integer $T$, the earliest time when everyone has finished eating.

5
2 2
7 7
1 3
6 4
8 5

17

Hint

Constraints: All input numbers are positive integers not exceeding $200$.

Translated by ChatGPT 5