Optimal Lunch Team Scheduling

At noon, after a morning training session, the THU ACM group goes to have lunch at the famous Shishi Canteen. There are two food‐dispensing windows and each window can serve only one person at a time. Each of the N group members requires a different amount of time to get served (depending on personal taste and appetite) and also takes a different amount of time to eat. The plan is to split the N people into two teams and, for each team, decide an order in which they line up at the respective window (team 1 goes to window 1 and team 2 to window 2). As soon as a person is served he immediately begins eating. All group members must finish eating before they can meet for their afternoon training.

For each person i (1 ≤ i ≤ N) a service time a_i and an eating time b_i are given. Once a team’s order is decided and processed at a window, the finishing time of the person in the j-th position (with j ≥ 1) is computed as

and the finishing time for that team is the maximum of all its finishing times. (Note that after being served, a person eats immediately and eating is done in parallel so they do not block each other.)

Your task is to partition the N people into two teams and determine the order in each team (optimally, each team’s tasks should be ordered in nonincreasing order of b values) so that the overall finish time (i.e. the maximum finishing time among the two teams) is minimized. Assume all people arrive at time 0.

Output the minimum possible time by which all group members can finish eating under the best plan.

inputFormat

The first line contains a single integer N (the number of people). Then N lines follow. Each of the next N lines contains two space‐separated integers a_i and b_i, representing the time required for person i to be served and the time required for person i to eat, respectively.

outputFormat

Output a single integer representing the minimum time by which all persons have finished eating.

sample

2
10 1
1 10

11