Fireworks in RightAngleles

In the city of RightAngleles the streets form an infinite square grid: every pair of streets is either parallel or perpendicular, and neighboring parallel streets are exactly one unit apart. Streets running West-East are called horizontal and are numbered by consecutive integers from South to North; streets running South-North are called vertical and are numbered by consecutive integers from West to East. Each intersection is identified by the number of its horizontal street and the number of its vertical street.

Every citizen lives at the intersection where their house entrance is located, and several citizens may live at the same intersection.

The mayor wants to hold a fireworks display at the intersection of the main horizontal street (numbered $0$) and some vertical street $V$. The fireworks are visible only along the two streets that meet there — the main horizontal street and vertical street $V$. For safety, every spectator must stand at least $S$ units away from the launch intersection. Concretely, a citizen may watch the display from either:

• an intersection on the main horizontal street whose vertical street number differs from $V$ by at least $S$, or
• an intersection on vertical street $V$ whose horizontal street number is at least $S$ away from $0$.

For example, when $S = 2$ the display may be watched from any intersection of the main horizontal street except those lying on vertical streets $V-1$, $V$, and $V+1$, and from any intersection of vertical street $V$ except those lying on horizontal streets $-1$, $0$, and $1$.

Citizens move only along the streets, so the distance a citizen walks to reach a watching spot equals the number of unit segments travelled. Each interested citizen walks to a nearest allowed watching spot, and the mayor chooses the vertical street $V$ so that the total distance walked by all citizens is as small as possible.

Write a program that computes this minimum possible total distance.

The first line contains two positive integers $N$ and $S$ separated by a space: the number of citizens $N$ ($N \le 10^5$) and the safety distance $S$ ($S \le 10^6$).

Each of the next $N$ lines contains two integers $H_i$ and $V_i$ separated by a space ($-10^9 \le H_i, V_i \le 10^9$): the horizontal street number $H_i$ and the vertical street number $V_i$ of the intersection where the $i$-th citizen lives.

Print a single integer: the minimum total distance (in units) that the citizens must walk in order to watch the fireworks.