Optimal Milk Scheduling

FJ has N cows that need to be milked every morning. The cows line up and go through two processes: the first process is performed by FJ and the second by Rob. It is given that if a cow starts the first process before another, she will also start the second process before the other.

For each cow, the time required for the first process is \(A_i\) and for the second process is \(B_i\). When cows wait between processes, one of the workers may be idle. For instance, if FJ takes a long time on a cow, Rob may remain idle until that cow finishes the first process; conversely, if FJ works quickly, a long queue may form before Rob.

Your task is to determine the minimum total time required to milk all cows when they are arranged in the optimal order.

Hint: Johnson's Rule

The classical solution involves splitting the cows into two groups:

• Group 1: cows with \(A_i \leq B_i\), sorted in ascending order of \(A_i\).
• Group 2: cows with \(A_i > B_i\), sorted in descending order of \(B_i\).

Then, simulate the process with two timers \(t_1\) and \(t_2\):

[ \begin{aligned} t_1 &= 0, \ t_2 &= 0, \ \text{For each cow } i: &&; t_1 &= t_1 + A_i, \ &&; t_2 &= \max(t_1, t_2) + B_i. \end{aligned} ]

The final answer is \(t_2\), the completion time after all cows have been processed.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 10⁵), the number of cows.

Each of the following N lines contains two space-separated integers \(A_i\) and \(B_i\) (1 ≤ \(A_i, B_i\) ≤ 10⁹), representing the processing times for the first and second processes respectively.

outputFormat

Output a single integer — the minimum total time required to milk all the cows.

sample

3
1 2
2 3
3 4

10