Description

Bessie runs a taxi service for the other cows along a fence of length $M$ ($1 \le M \le 10^9$). There are $N$ cows ($1 \le N \le 10^5$). Cow $i$ starts at position $a_i$ and wants to go to position $b_i$ ($0 \le a_i, b_i \le M$). Bessie starts at the leftmost point, position $0$, must finish at the rightmost point, position $M$, and wants to minimize the total distance she drives.

Bessie’s car can carry only one cow at a time. Cows can enter and exit the car instantaneously. To save gas, Bessie may drop a cow off at an intermediate position before reaching that cow’s destination.

Determine the minimum total distance Bessie must drive to complete all rides and end at position $M$.

Input Format

• Line 1: $N$ and $M$ separated by a space.
• Lines $2..1+N$: The $(i+1)$‑th line contains two space‑separated integers, $s\_i$ and $t\_i$ ($0 \le s\_i, t\_i \le M$), indicating the starting position and destination position of the $i$‑th cow.

Output Format

• Line 1: A single integer indicating the total amount of driving Bessie must do. Note that the result may not fit into a 32‑bit integer.

2 10 
0 9 
6 5 

12 

Hint

There are two cows waiting along a fence of length $10$. The first cow wants to go from position $0$ (where Bessie starts) to position $9$. The second cow wishes to go from position $6$ to position $5$.

Bessie picks up the first cow at position $0$ and drives to position $6$. There she drops off the first cow, delivers the second cow to her destination, and returns to pick up the first cow. She then drops off the first cow and drives the rest of the way to position $10$.

Translated by ChatGPT 5