Fireworks Optimization on Grid

This problem is set in an infinite grid city, where some citizens reside at the intersections (note that multiple citizens can reside at the same intersection). A fireworks display is to be held at the intersection of the horizontal street y = 0 and some vertical street x = a (where a is an integer that you need to choose).

To watch the fireworks, each citizen will travel to one of the two streets that passes through the fireworks location (i.e. either the vertical street x = a or the horizontal street y = 0). However, for safety reasons, when a citizen reaches the chosen street they must be at least a distance S away from the fireworks display. More formally, if a citizen chooses to watch on the vertical street, they can meet at any point (a, y) with |y| \ge S (and their travel distance on that street will be |y - y_i|). Similarly, if they choose the horizontal street, they can meet at any point (x, 0) with |x - a| \ge S (and their travel distance on that street will be |x - a| from the fireworks location); however, the citizen first must travel vertically from (x_i, y_i) to (x_i, 0) before doing any additional adjustments. In each case, the citizen will choose the option that minimizes his/her travel distance.

More precisely, suppose a citizen lives at (x_i, y_i) and the fireworks are set off at (a, 0). They have two options:

1. Go to the vertical street x = a:
   They move horizontally from (x_i, y_i) to (a, y_i) at a cost of |xi - a|. If |yi| < S, then in order to ensure safe distance from the fireworks at (a, 0) (which is |y| when on this vertical street), they need to travel an additional cost of S - |yi|. Hence, the total cost for this option is:

$$cost_{vertical} = |x_i - a| + \max(0, S - |y_i|)$$

1. Go to the horizontal street y = 0:
   They move vertically from (x_i, y_i) to (x_i, 0) at a cost of |yi|. If |xi - a| < S, then to be safe they must travel further horizontally along the road by S - |xi - a|. Hence, the total cost for this option is:

$$cost_{horizontal} = |y_i| + \max(0, S - |x_i - a|)$$

Each citizen will choose the option that minimizes their personal travel cost, i.e.,

$$cost_i = \min\Big(|x_i - a| + \max(0, S - |y_i|), \; |y_i| + \max(0, S - |x_i - a|)\Big)$$

Your task is to choose an integer a (i.e. a vertical street) that minimizes the total travel distance summed over all citizens, and then output that minimum total distance.

---

Input Format:

• The first line contains two integers N and S.
• The following N lines each contain two space-separated integers representing the coordinates x_i and y_i of a citizen.

Output Format:

• Output a single integer, the minimum total travel distance for all citizens.

Constraints (not explicitly given): You may assume that N is up to 10⁵ and the coordinates and S have absolute values up to 10⁹. It is guaranteed that an optimal solution exists.

inputFormat

The input is given as follows:

N S
x1 y1
x2 y2
... 
 xN yN

outputFormat

Output a single integer representing the minimum total travel distance required for all citizens.

sample

3 1
0 0
2 2
1 -1

1