Manure Teleporter

The farm chore Farmer John dislikes most is hauling large amounts of manure. To cut the work down he builds a manure teleporter. Instead of driving a cart behind his tractor between two points, he sends manure from one location to another instantly.

Farmer John's farm lies along a single straight road, so every location on it is described by one coordinate along that road, a point on the number line. A teleporter is described by two numbers $x$ and $y$: manure brought to location $x$ is transported instantly to location $y$.

Farmer John puts one endpoint at $x = 0$ and has to choose where the other endpoint $y$ goes. There are $N$ piles of manure on the farm ($1 \le N \le 100{,}000$). Pile $i$ must be moved from position $a_i$ to position $b_i$, and each pile is transported separately. Let $d_i$ be the distance Farmer John drives with pile $i$ in his tractor. Hauling it directly gives $d_i = |a_i - b_i|$. Using the teleporter means driving from $a_i$ to $x$ and then from $y$ to $b_i$, which gives $d_i = |a_i| + |y - b_i|$. Farmer John takes the shorter of the two routes. The same $y$ is used while every pile is transported.

Choose $y$ so the sum of the $d_i$ is as small as possible, and report that sum.

The first line contains $N$. Each of the next $N$ lines contains $a_i$ and $b_i$, both integers in the range $-10^8$ to $10^8$. The values are not necessarily distinct.

Print the minimum sum of the $d_i$ as a single integer. The value can exceed the range of a 32-bit integer, so use a 64-bit integer type in languages that need one.

In the first example, setting $y = 8$ gives $d_1 = 2$, $d_2 = 5$ and $d_3 = 3$. Any $y$ between $7$ and $10$ gives the same sum.