Taxi

Bessie is running a taxi service for the other cows on the farm. The cows have gathered at different locations along a fence of length $M$ ($1 \le M \le 10^9$). They have grown bored with their current spots and each wishes to move somewhere else along the fence. Bessie must pick up each cow at its starting position and drive it to its destination.

Bessie's car is small, so she can transport only one cow at a time. Cows can enter and exit the car instantaneously.

To save gas, Bessie wants to minimize the total distance she drives. Given the starting and ending positions of each of the $N$ cows ($1 \le N \le 10^5$), determine the least amount of driving Bessie has to do. To save the most gas, she may occasionally need to drop a cow off at a position other than its destination.

Bessie starts at the leftmost point of the fence, position $0$, and must finish her journey at the rightmost point, position $M$.

• Line 1: Two space-separated integers $N$ and $M$.
• Lines 2 to $N+1$: Line $i+1$ contains two space-separated integers $s_i$ and $t_i$ ($0 \le s_i, t_i \le M$), the starting position and destination of the $i$-th cow.

• Line 1: A single integer, the minimum total distance Bessie must drive. Note that the result may not fit in a 32-bit integer.

It helps to notice that Bessie does not have to drive each cow straight to its destination. By dropping a cow at an intermediate point and picking it up later, she can sometimes shorten the distance she spends driving with an empty car.

The total distance splits into two parts. First, moving each cow from its start to its destination always costs $\sum_i |s_i - t_i|$. Second, there is the empty driving needed to reposition between one drop-off and the next pick-up. The set of points where an empty trip can begin is $\{0\} \cup \{t_i\}$, and the set of points where one can end is $\{s_i\} \cup \{M\}$; sorting both sets and pairing them in order minimizes the total empty distance.