Teleportation (Silver)#10410
One of the farm chores Farmer John dislikes most is hauling around large amounts of cow manure. To streamline this process, he has come up with a brilliant invention: the manure teleporter! Instead of hauling manure between two points in a cart behind his tractor, he can use the manure teleporter to transport manure instantly from one location to another.
Farmer John's farm is built along a single long straight road, so any location on the farm can be described simply by its position along this road (effectively, a point on the number line). A teleporter is described by two numbers and : manure brought to location can be instantly transported to location .
Farmer John has decided to build a teleporter with its first endpoint at x = 0. Your task is to help him choose the best position for the other endpoint . Specifically, there are n~(1 \le n \le 10^5) piles of manure on his farm. The -th pile needs to be moved from position a_i to position b_i, and Farmer John transports each pile separately. Let d_i denote the distance Farmer John drives his tractor with manure while hauling the -th pile. If he hauls the -th pile directly with the tractor, then d_i = |a_i - b_i|; if he uses the teleporter (for example, hauling the pile with his tractor from a_i to and then from to b_i), d_i may turn out to be smaller.
Help Farmer John determine the minimum possible sum of the values d_i he can achieve by placing the other endpoint of the teleporter at an optimally chosen position. The same position is used for transporting every pile.
The first line contains the integer . Each of the next lines contains two integers a_i and b_i~(-10^8 \le a_i, b_i \le 10^8). These values are not necessarily distinct.
Print one integer — the minimum sum of the values d_i Farmer John can achieve. Note that this number may not fit into a standard -bit integer type, so you may need a -bit integer type such as long long in C/C++.
In this example, by setting y = 8, Farmer John can achieve d_1 = 2, d_2 = 5 and d_3 = 3. Note that any value of in the range also yields an optimal solution.
Example 1