Maximizing Bamboo Coverage

You are given n bamboo poles. The i-th pole has a length \(a_i\) and a mark located at a distance \(b_i\) from one end. All poles must be placed on a line so that their marks are aligned at the same point. For each pole you are allowed to flip its orientation (i.e. swap its ends) when placing it. When a pole of length \(a\) with a mark at \(b\) is placed and its mark is aligned to a fixed point (say, \(0\)), it will cover an interval on the line. In one orientation the pole covers \([-b, a-b]\) and in the flipped orientation it covers \([-(a-b), b]\). Since every pole covers the alignment point, the union of all intervals is contiguous and equals \([L, R]\), where \(L = \min_{1\le i\le n}\,L_i\) and \(R = \max_{1\le i\le n}\,R_i\) (with \(L_i, R_i\) chosen according to the orientation of pole \(i\)).

Your goal is to choose an orientation for each bamboo so that the total length of the line covered by the poles, i.e. \(R - L\), is maximized. Compute this maximum possible covered length.

Note: For each pole, if we denote \(X = a_i - b_i\) and \(Y = b_i\), then the two possible placements yield intervals:

• Non-flipped: \(\big[-Y, X\big]\), with covered length \(X+Y=a_i\).
• Flipped: \(\big[-X, Y\big]\), with covered length \(X+Y=a_i\).

Although each pole individually covers a length equal to its own length \(a_i\), the overall covered segment (the union of all intervals) has endpoints determined by the pole that extends farthest to the left and the pole that extends farthest to the right. You must use all the poles (each in one of the two possible orientations). It turns out that the maximum union length is given by picking one pole (say, pole \(i\)) to achieve the extreme left endpoint and a different pole (say, pole \(j\)) to achieve the extreme right endpoint. In particular, if for a pole we define \(M_i = \max(b_i, a_i-b_i)\) (the maximum extension it can provide in one direction), then if we choose two distinct poles with the top two values of \(M_i\), the union may extend to \(-M_i\) on the left (using the corresponding orientation) and to \(M_j\) on the right (using the other pole’s best orientation), yielding a union length of \(M_i + M_j\). However, if there is only one pole or if the best achievable sum using two different poles is less than the length of a single pole, then the answer is simply \(a_i\) for the best pole. In summary, the answer is:

[ \text{answer} = \begin{cases} a_i & \text{if } n=1,\ \max\Bigl(\max_{1\le i\le n} a_i,; M_{(1)} + M_{(2)}\Bigr)& \text{if } n\ge 2, \end{cases} ]

where \(M_{(1)}\) and \(M_{(2)}\) are the largest and second largest values among \(\{M_i : 1\le i\le n\}\), respectively.

inputFormat

The input begins with an integer \(n\) (the number of bamboo poles). Each of the next \(n\) lines contains two integers \(a_i\) and \(b_i\) separated by spaces, representing the length of the pole and the distance of the mark from one end.

It is guaranteed that \(1 \le n \le 10^5\) and \(1 \le b_i < a_i \le 10^9\).

outputFormat

Output a single integer: the maximum possible length of the line covered by the bamboo poles when placed optimally.

sample

1
10 3

10