分数: 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