配点 : $800$ 点

問題

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

ニワンゴくんはレアな黒いテレビちゃんのぬいぐるみを $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$ 点を同時に回転させる

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

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

制約

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

入力

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

$N$ $D$

$x_1$ $y_1$

$:$

$x_N$ $y_N$

出力

答えを出力せよ。

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