Minimum Number of Cow Sheds

You are given 10⁹ cow sheds arranged in a line from left to right. You wish to place n cows into some of these sheds. However, the cows are very combative. For the i-th cow, its attack range is given as \((a_i, b_i)\). This means that if there is any other cow within the a_i sheds to its left or within the b_i sheds to its right, it will start a fight.

You want to keep a contiguous block of cow sheds (and sell the rest) so that it is possible to arrange all n cows in the remaining sheds without any cow causing trouble. Find the minimum number of sheds you must keep to achieve this.

Note on boundaries: For a cow placed in a shed near the end of the block, only the existing sheds in its attack range are considered. That is, if a cow only has fewer than a_i sheds on its left (or fewer than b_i sheds on its right) because it is at the boundary, then only those available sheds are considered; missing sheds do not cause any conflict.

Arrangement details:

Assume you label the sheds in the chosen contiguous block as positions 1 through L (where L is the number of sheds kept). You need to assign each cow to a distinct position such that for the cow placed at a position, if there is a cow in any of the next a_i positions to its left (if they exist) or in any of the next b_i positions to its right (if they exist), a fight will occur.

Your task is to compute the minimum L such that there exists an ordering of the n cows and an assignment of positions satisfying the condition. It can be shown that if you determine a permutation \(P\) of the cows and let their positions be \(x_1 < x_2 < \cdots < x_n\) within the block, then in order to keep each cow peaceful the following must hold:

• For each cow \(P(j)\) with \(j \ge 2\): \(x_j - x_{j-1} > a_{P(j)}\).
• For each cow \(P(j)\) with \(j \le n-1\): \(x_{j+1} - x_j > b_{P(j)}\).

By setting the gaps \(g_j = x_{j+1} - x_j - 1\) (i.e. the number of empty sheds between consecutive cows), the minimal total number of sheds needed is

[ L = n + \min_{P} \sum_{j=1}^{n-1} \max(b_{P(j)}, a_{P(j+1)}) ]

It turns out that an optimal strategy is to sort the cows in descending order of \(a_i\) (and if two cows have the same \(a_i\), sort by ascending \(b_i\)). Then, the minimum number of sheds required is computed as:

[ L = n + \sum_{j=1}^{n-1} \max(b_{P(j)}, a_{P(j+1)}) ]

Your task is to implement this calculation.

inputFormat

The first line contains a single integer n (\(1 \le n \le 10^5\)) representing the number of cows. Each of the next n lines contains two non‐negative integers \(a_i\) and \(b_i\) (\(0 \le a_i, b_i \le 10^9\)), representing the attack range of the i-th cow.

outputFormat

Output a single integer representing the minimum number of sheds that must be kept so that there exists an arrangement where all cows can be placed with no conflicts.

sample

1
0 0

1