Minimizing the Maximum Bonus

The Queen has n ministers. Each minister has a positive integer written on his left hand and another positive integer on his right hand. On National Day, the Queen awards a bonus to each minister. Under the original arrangement the bonus for the i-th minister is determined by the following rule:

$$ c_{i} = \begin{cases} a_{1}+b_{1} & ,\; i=1, \\ \displaystyle \max \Big\{ c_{i-1}, \sum_{j=1}^{i} a_{j} \Big\} + b_{i} & ,\; 2\leq i \leq n \end{cases} $$

Here, for the i-th minister, a_i is the number on the left hand and b_i is the number on the right hand. Note that because of the recurrence the bonus is non‐decreasing among the ministers. In other words, the maximum bonus under any arrangement is the bonus received by the last minister in the queue.

The stingy Queen does not want too much money to be given out. Therefore, she allows you to rearrange the order of the ministers (possibly keeping some positions unchanged) so that the maximum bonus among all the ministers is as small as possible.

---

Problem Analysis

Given a permutation p of the ministers, the bonus of the minister at position i is computed as follows. Let the ordered sequence be \((a_{p_1}, b_{p_1}), (a_{p_2}, b_{p_2}), \dots, (a_{p_n}, b_{p_n})\). Then,

$$ c_{p_1} = a_{p_1} + b_{p_1}, \quad \text{and} \quad c_{p_i} = \max \Big\{ c_{p_{i-1}}, \sum_{j=1}^{i} a_{p_j} \Big\} + b_{p_i}, \; \text{for } 2 \le i \le n. $$

Your task is to find an ordering which minimizes c_{p_n} (note that the sum \(\sum_{j=1}^{n} a_{p_j}\) is invariant, so it is equivalent to minimizing the extra accumulation as a result of the bonuses added along the way).

A useful observation is that the recurrence can be reinterpreted by defining an extra penalty P such that after processing a minister \((a, b)\) the update is given by:

$$P \leftarrow \max(P - a, 0) + b.$$

The final bonus is then total_a + P where total_a is the sum of all the a_i values. It turns out that an optimal strategy is similar to Johnson's rule in two‐machine flow shop scheduling. Specifically, partition the ministers into two groups:

• Group 1: Ministers with \(a_i \le b_i\). Sort these in increasing order of \(a_i\).
• Group 2: Ministers with \(a_i > b_i\). Sort these in decreasing order of \(b_i\).

Then, the optimal order is to place all ministers in Group 1 before those in Group 2. Finally, simulate the bonus distribution in that order.

inputFormat

The first line contains a single integer n (\(1 \le n \le 10^5\)) -- the number of ministers.

Each of the following n lines contains two positive integers \(a_i\) and \(b_i\) (\(1 \le a_i, b_i \le 10^9\)), representing the number written on the left hand and right hand of the i-th minister.

outputFormat

Output a single integer -- the minimum possible value of the maximum bonus (i.e. the bonus of the last minister in the arranged order) after reordering optimally.

sample

2
1 10
10 1

12