分数: 525 点
问题陈述
有 N 点标记 1, 2, \dots, N 上 xy- 平面。点 i 位于坐标处 (X_i, Y_i).
您可以在以下时间之间执行以下操作: 0 和 K 次,含在内。
- 首先,选择其中一个 N 点。让 k 是选定的点,并假设它当前位于 (x, y).
- 接下来,选择并执行以下四个操作之一:
- 移动点 k 沿 x- 轴 +1。点的坐标 k 成为 (x+1, y).
- 移动点 k 沿 x- 轴 -1。点的坐标 k 成为 (x-1, y).
- 移动点 k 沿 y- 轴 +1。点的坐标 k 成为 (x, y+1).
- 移动点 k 沿 y- 轴 -1。点的坐标 k 成为 (x, y-1).
- 同一坐标处允许有多个点。请注意,输入可能已经在同一坐标处有多个点。
完成所有操作后,绘制一个包含所有 N 点在圆周内部或圆周上,每条边平行于圆周 x- 或 y- 轴。
找到该正方形边长的最小可能值。该值可以显示为整数,因为所有点始终位于格点上。
特别是,如果可以使所有点存在于同一坐标处,则答案被认为是 0.
约束
- 所有输入值均为整数。
- 1 \le N \le 2 \times 10^5
- 0 \le K \le 4 \times 10^{14}
- 0 \le X_i, Y_i \le 10^9
输入
输入由标准输入按以下格式给出:
N K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
输出
将答案打印为整数。
样本输入 1
6 5 2 0 5 2 0 3 3 2 3 4 1 5
示例输出 1
3
下图以水平方向说明了这种情况 x-轴和垂直 y- 轴。

例如,按照图中箭头执行四次移动后,可以包含图中边长为 的正方形内部或圆周上的所有点 3,这可以显示为最小值。
示例输入 2
4 400000000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
示例输出 2
0
所有点从一开始就已经存在于相同的坐标处。
例如,通过执行零运算,可以使所有点存在于同一坐标处,因此该输入的答案是 0.
示例输入 3
10 998244353 489733278 189351894 861289363 30208889 450668761 133103889 306319121 739571083 409648209 922270934 930832199 304946211 358683490 923133355 369972904 539399938 915030547 735320146 386219602 277971612
示例输出 3
484373824