Problem Description

NiwanGo loves fireworks. Tonight, as NiwanGo is returning home from work, there is a fireworks festival taking place.

The path from NiwanGo's office to his home is a straight line, which can be considered as a number line. The coordinates of the office are $0$, and the coordinates of NiwanGo's home are $L$.

Tonight, a total of $N$ fireworks will be launched. The $i$-th ($1 \leq i \leq N$) firework will be launched at time $t_i$ at position $P_i$ ($0 \leq P_i \leq L$).

NiwanGo can walk on the path from the office to his home at any speed, but he will not turn back. However, he can stop along the way.

NiwanGo wants to see the fireworks as close as possible. Therefore, he wants to minimize the sum of the absolute differences between his position and the position of the fireworks at their launch times.

That is, if $f(t)$ denotes the coordinate where NiwanGo is at time $t$, he wants to set a non-decreasing function $f(t)$ from real numbers to real numbers to minimize the sum of $|f(t_i) - P_i|$ for all $i$.

Please solve this problem on behalf of NiwanGo.

Input Format

The input is given from the standard input in the following format:

$N$ $L$ $t_1$ $P_1$ ... $t_N$ $P_N$

• The first line contains two integers $N$ ($1 \leq N \leq 10^5$) and $L$ ($1 \leq L \leq 10^5$) separated by a space.
• The following $N$ lines contain the launch time and position of the $i$-th firework, represented by integers $t_i$ ($1 \leq t_i \leq 10^5$) and $P_i$ ($0 \leq P_i \leq L$) separated by a space.
• For all $i$ ($1 \leq i \leq N-1$), $t_i \leq t_{i+1}$ is satisfied. If $t_i = t_{i+1}$, then $P_i \leq P_{i+1}$ is satisfied.
• Fireworks may be launched at the same time and position.

Output Format

Output the minimum sum of the absolute differences between NiwanGo's position at the launch time and the position of the fireworks for all fireworks in one line. Note that this value can be proven to be an integer. Be aware that the output value may exceed the range of a 32-bit signed integer.

Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 10
1 2
1 4
3 8
4 7
5 1

Sample Output #1

9

Sample Input #2

4 10
1 4
1 4
2 1
3 9

Sample Output #2

3

Sample Input #3

10 20
2 15
3 4
3 14
4 11
6 0
7 7
8 8
8 8
8 12
9 10

Sample Output #3

33

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N \leq 2000$, $L \leq 2000$, and $t_i \leq 2000$ correctly, you will be awarded 30 points as partial credit.

Sample Explanation 1

By moving to coordinate $3$ at time $1$, to coordinate $7$ at time $3$, and to the home at coordinate $10$ at time $6$, the sum of the absolute differences between NiwanGo's position and the position of the fireworks at their launch times can be $9$. It is not possible to achieve a smaller value, so output $9$.

Sample Explanation 2

Fireworks may be launched at the same time and position.

见题面 Input 部分

见题面 Output 部分