题目描述

ドワンゴ社員のニワンゴくんはテレビちゃんが大好きなので、テレビちゃんのぬいぐるみを大量に集めて床に一面に並べていました。

ニワンゴくんはレアな黒いテレビちゃんのぬいぐるみを $N$ 個持っていて、普通のテレビちゃんのぬいぐるみと一緒に並べていました。しかし、あちこちに置いておくと管理が難しいので近くにまとめることにしました。

無限に広い二次元平面上のすべての格子点上にぬいぐるみが置いてあります。$N$ 個の黒いぬいぐるみの座標 $(x_i,y_i)$ が与えられます。ぬいぐるみは点として扱います。

ニワンゴくんは以下の操作を任意の回数行うことができます。

• 辺が軸に平行な一辺の長さが $D$ の正方形を、各頂点が格子点と重なるように任意の座標に置き、正方形の角の $4$ 点を、そこにある $4$ 個のぬいぐるみと一緒に $90$ 度回転させる。つまり、正方形の左下の頂点を $(x,y)$ とした場合、$ (x,y)\ \rightarrow\ (x+D,y)\ \rightarrow\ (x+D,y+D)\ \rightarrow\ (x,y+D)\ \rightarrow\ (x,y) $ の順に、$4$ 点を同時に回転させる

配置の乱雑さを、すべての黒いぬいぐるみを囲うのに必要な辺が軸に平行な正方形の一辺の長さの最小値とします。 ここで、正方形の辺上にあるぬいぐるみも正方形に囲われているものとします。

ニワンゴくんが何度か操作を行ったあとの乱雑さとしてありうる値のうち、最小値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

答えを出力せよ。

题目大意

在无限大的二维平面中有 $N$ 个黑点：$(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)$，剩余的点均为白点，你可以按以下规则进行无限次操作：

• 选择一个边长为 $D$ 的正方形，并将其四个角上的点进行旋转，具体来说选择了一个左下角 $(x,y)$ 的正方形，会按以下顺序旋转：$(x,y)\rightarrow(x+D,y)\rightarrow(x+D,y+D)\rightarrow(x,y+D)\rightarrow(x,y)$

定义两个点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的距离为 $\max(\lvert x_1-x_2\rvert,\lvert y_1-y_2\rvert)$，你需要通过任意次操作使得平面上距离最远的两黑点的距离最小，并输出这一最小距离

3 1
0 0
1 0
2 0

1

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

4

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

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$ 点が与えられる