题目描述

译自 BalticOI 2012 Day2 T1. Fireworks in RightAngleles

在 RightAngleles 市，无数条竖直的街道和水平的街道交织成网状。城市中的任意两条街道彼此平行或垂直，并且任意两条相邻的平行街道的距离是相同的（我们定义两条相邻的平行街道的距离为一个单位长度）。城市中东西向的街道称为水平街道，这些街道按照从北向南的顺序进行编号；城市中南北向的街道称为竖直街道，这些街道按照从西向东的顺序进行编号。

城市的每个市民都住在一栋房子里，所有的房子都位于水平街道与竖直街道的交点。可能有多个市民住在同一个房子中。

现在市长想要在城市主干道（编号为 $0$ 的水平街道）和某条竖直街道的交点处举行烟花表演。市民可以在烟花燃放地点所处的水平街道和竖直街道处看到烟花。为了安全起见，观看烟花的市民与烟花燃放地点的距离不得小于 $S$ 个单位长度。这意味着，如果烟花燃放地点在城市主干道和编号为 $V$ 的竖直街道的交点处，市民必须在城市主干道或是编号为 $V$ 的竖直街道处观赏烟花，且他们离燃放地点的距离不得小于 $S$ 个单位长度。

燃放烟花的效果取决于市民观赏烟花需要移动的距离，因此，市长希望所有市民为观赏烟花移动的距离总和最小。

输入格式

输入第一行两个整数 $N,S$，分别代表市民的总数和安全距离。

接下来 $N$ 行，每行两个整数 $H_i,V_i$，表示第 $i$ 位市民居住的房子位于编号为 $H_i$ 的水平街道和编号为 $V_i$ 的竖直街道的交点处。

输出格式

输出一个整数，即所有市民为观赏烟花移动的距离和的最小值。

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

9

数据范围与提示

• 对于 $20\%$ 的数据，$0 \leq V_i \leq 5000$；
• 对于 $40\%$ 的数据，$N \leq 5000$；
• 对于 $100\%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq S \leq 10^6$，$-10^9 \leq H_i,V_i \leq 10^9$。