题目描述

Dwango公司的员工Niwango君非常喜欢虎牙TV，所以他收集了很多她的玩偶，并把它们摆放在地板上。

Niwango君有N个黑色稀有虎牙TV玩偶，它们和普通玩偶一起摆放在一起。他希望这些黑色稀有虎牙TV玩偶能够靠得更近一些，所以他决定重新安排它们的位置。

在一个无限大的二维平面上，每个格点都有一个玩偶。给出N个黑色稀有虎牙TV玩偶的坐标$(x_i,y_i)$。所有玩偶被认为是点（没有长度、面积或体积）。

他可以任意多次进行以下操作：

• 放置一个边长为D的轴对齐正方形，将正方形按顺时针旋转90度，四个角落上各放一个玩偶。更具体地说，如果左下角的坐标是$(x, y)$，则依次按照顺序旋转四个点$(x,y) \\rightarrow (x+D,y) \\rightarrow (x+D,y+D) \\rightarrow (x,y+D) \\rightarrow (x,y)$。正方形的四个角必须位于格点上。

让我们定义安排的散布度是能够包围所有黑色稀有虎牙TV玩偶的最小边长的轴对齐正方形。正方形的边缘上或角点上的黑色稀有虎牙TV玩偶被认为是被正方形包围的。

在他进行任意次操作后，找到散布度的最小值。

约束条件

• $2 \leq N \leq 10^5$
• $1 \leq D \leq 1000$
• $0 \leq x_i, y_i \leq 10^9$
• 给定的坐标两两不同
• 输入中给出的所有数字都是整数

分值细则

• 得分500分的测试用例满足$1 \leq D \leq 30$。

输入

输入从标准输入读取，格式如下：

$N$ $D$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出

输出答案。

输入示例1

3 1
0 0
1 0
2 0

输出示例1

1

输入示例2

19 2
1 3
2 3
0 1
1 1
2 1
3 1
4 4
5 4
6 4
7 4
8 4
8 3
8 2
8 1
8 0
7 0
6 0
5 0
4 0

输出示例2

4

输入示例3

8 3
0 0
0 3
3 0
3 3
2 2
2 5
5 2
5 5

输出示例3

4