Description

This is a city with infinitely many grid-like streets. Some citizens live at the intersection points of the grid. (It is possible that two citizens live at the same place.)

Now you need to choose an intersection point between some vertical street and horizontal street $0$ as the place to set off fireworks. Citizens must come to either the horizontal street or the vertical street that contains this point to watch. At the same time, their distance to the fireworks location must not be less than $S$. You need to choose a fireworks location to minimize the total moving distance of all citizens.

Input Format

The first line contains two integers $N$, $S$, representing the total number of citizens and the minimum distance, respectively.

The next $N$ lines each contain two integers $H_i$, $V_i$, meaning that this citizen lives at the intersection of horizontal street $H_i$ and vertical street $V_i$.

Output Format

Output the minimum possible sum of moving distances.

7 2
3 -2
0 8
-4 8
-1 4
-2 13
-4 8
1 5

9

Hint

Sample Explanation

Note that there are two people living at the intersection of horizontal street $-4$ and vertical street $8$.

The optimal solution is to choose vertical street $8$, and then the minimum total distance is $9$.

Constraints

• For $20\%$ of the testdata, $0 \leq V_i \leq 5000$.
• For $40\%$ of the testdata, $N \leq 5000$.
• For $100\%$ of the testdata, $1 \leq N \leq 10^5$, $1 \leq S \leq 10^6$, $-10^9 \leq H_i, V_i \leq 10^9$.

Notes

Translated from BalticOI 2012 Day2 T1. Fireworks in RightAngleles.

Translated by ChatGPT 5