Manure Teleporter Optimization

Farmer John is tired of hauling manure manually along his farm’s long straight road. To help him out, he invents a manure teleporter that instantly transports manure from point x = 0 to some other chosen point y (which must be the same for every use).

There are N piles of manure. The i-th pile must be moved from position a_i to b_i. If Farmer John hauls the pile directly with his tractor, he drives a distance of \(|a_i-b_i|\). Alternatively, he can use the teleporter by driving from a_i to 0, teleporting instantly, and then driving from y to b_i, incurring a distance of \(|a_i|+|y-b_i|\>.

For each pile, he chooses the method (direct or via teleporter) that minimizes the distance traveled. Your task is to determine the optimal position y (other than 0) so that the total driving distance over all piles is minimized.

Mathematical formulation:

For the i-th pile, the cost is \[ d_i = \min\Bigl(|a_i-b_i|,\;|a_i|+|y-b_i|\Bigr). \] The goal is to choose y to minimize the total cost: \[ \text{Total Cost} = \sum_{i=1}^{N} d_i. \]

Hint: Notice that for each pile, using the teleporter is beneficial only if \[ |a_i|+|y-b_i| 0\), teleporter use yields a saving of \(T_i - |y-b_i|\) provided that \(|y-b_i| < T_i\) (otherwise the direct method is better). Hence, the maximum saving attainable by using the teleporter with endpoint y is \[ \sum_{i\,:\, T_i>0} \max\bigl(0, T_i - |y-b_i|\bigr). \] The optimal total driving distance is then \[ \sum_{i=1}^{N} |a_i-b_i| - \max_{y}\Bigl\{\sum_{i\,:\, T_i>0} \max\bigl(0, T_i - |y-b_i|\bigr)\Bigr\}. \]

inputFormat

The first line contains a single integer N (\(1 \leq N \leq 100,000\)). Each of the following N lines contains two space‐separated integers representing a_i and b_i.

All positions are given on a one-dimensional number line.

outputFormat

Output a single integer: the minimum total distance Farmer John must drive after optimally choosing y for the teleporter.

sample

3
-5 -1
2 10
3 1

8