← 返回题目列表

AtCoder · dwacon5th_prelims_d

D. 方形旋转

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

Dwango Co., Ltd.的员工Niwango-kun喜欢Niconico TV-chan,所以他收集了很多她的毛绒玩具并将它们铺在地板上。

二王后君有 N niconico TV酱的黑色稀有毛绒玩具,与普通玩具一起传播。他希望这些黑色的稀有毛绒玩具能够靠得很近,所以他决定重新排列它们。

在无限大的二维平面中,每个格点上都有一个毛绒玩具。坐标 (x_i,y_i) of N 黑色稀有毛绒玩具。所有毛绒玩具都被视为点(没有长度、面积或体积)。

他可以任意多次执行以下操作:

  • 放置一个边长与轴对齐的正方形 D,将正方形旋转 90 度在正方形的四个角上放置四个毛绒玩具。更具体地说,如果左下角的坐标是 (x, y),旋转四点 (x,y) \rightarrow (x+D,y) \rightarrow (x+D,y+D) \rightarrow (x,y+D) \rightarrow (x,y) 按此顺序。正方形的四个角必须都在一个格点上。

让我们定义 分散度 由包围全黑色稀有毛绒玩具的轴对齐正方形的最小边长排列。正方形边缘或顶点上的黑色稀有毛绒玩具被视为被正方形包围。

求他执行任意多次操作后的最小分散度。

约束

  • 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