题目描述

由于非常喜欢电视酱，dwango 的员工 Niwango 君收集了大量的电视酱玩偶，并将它们铺满了地板。

Niwango 君拥有 $N$ 个稀有的黑色电视酱玩偶，并将它们与普通的电视酱玩偶一起摆放。然而，分散地摆放管理起来很困难，所以他决定把它们集中到一起。

在无限广阔的二维平面上，每一个格点上都放有一个玩偶。给定 $N$ 个黑色玩偶的坐标 $(x_i, y_i)$。玩偶视为点。

Niwango 君可以进行任意次数如下操作：

• 可以在任意坐标上放置一个边长为 $D$、边与坐标轴平行、每个顶点都在格点上的正方形，然后将正方形四个角上的 $4$ 个点（即 $4$ 个玩偶）一起顺时针旋转 $90$ 度。具体来说，若正方形的左下角为 $(x, y)$，则 $(x, y) \rightarrow (x+D, y) \rightarrow (x+D, y+D) \rightarrow (x, y+D) \rightarrow (x, y)$，四个点同时按此顺序旋转。

定义乱杂度为：包围所有黑色玩偶所需的、边与坐标轴平行的正方形的最小边长。这里，正方形边上的玩偶也视为被包围。

请你求出 Niwango 君经过若干次操作后，乱杂度可能达到的最小值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $D$ $x_1$ $y_1$ $x_2$ $y_2$ $\ldots$ $x_N$ $y_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 1
0 0
1 0
2 0

输出 #1

1

输入输出样例 #2

输入 #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

输入 #3

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

输出 #3

4

说明/提示

限制

• $2 \leq N \leq 10^5$
• $1 \leq D \leq 1000$
• $0 \leq x_i, y_i \leq 10^9$
• 给定的所有坐标均不相同
• 输入的所有数值均为整数

部分分

• 对于满足 $1 \leq D \leq 30$ 的数据集，得分为 $500$ 分。