AT_dwacon5th_prelims_d Square Rotation

由于非常喜欢电视酱，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$

请输出答案。

## 限制 - $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$ 分。 由 ChatGPT 4.1 翻译