题目描述

这是一座有着无限网格状街道的城市，有一些市民住在网格的交点处。(可能会有两个市民住在相同的地方)

现在你需要选择某个竖直街道与水平街道 $0$ 的交点处进行烟花表演，市民需要赶到这个地点所在的水平街道或竖直街道上来观看，同时他们离燃放地点的距离不能小于 $S$。你需要选择一个燃放地点以最小化市民们的移动距离。

输入格式

第一行两个整数 $N$，$S$，分别代表市民总数和最小距离。

接下来 $N$ 行每行两个整数 $H_i$，$V_i$，表示这位市民住在水平街道 $H_i$ 与 竖直街道 $V_i$ 交点处。

输出格式

输出移动距离和的最小值。

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

9

提示

【样例解释】

注意水平街道 $-4$ 与竖直街道 $8$ 交点处有两个人居住。

最优解是选择竖直街道 $8$，此时距离取最小值 $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$

【说明】

译自 BalticOI 2012 Day2 T1. Fireworks in RightAngleles