最小化外接正方形

题目描述

平面上有编号为 $1, 2, \dots, N$ 的 $N$ 个点。点 $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)$。

允许多个点位于同一坐标。注意,输入中可能已经存在多个点位于同一坐标的情况。

在所有操作结束后,画一个正方形,使其各边与 $x$ 轴或 $y$ 轴平行,并把所有 $N$ 个点都包含在内部或边上。

求这个正方形边长的最小可能值。由于所有点始终位于整点上,可以证明该值一定是整数。

特别地,如果可以让所有点位于同一坐标,则答案视为 $0$。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$X_1$ $Y_1$
$X_2$ $Y_2$
$\vdots$
$X_N$ $Y_N$

输出格式

以整数形式输出答案。

样例

6 5
2 0
5 2
0 3
3 2
3 4
1 5

3

例如,执行 4 次移动后,可以把所有点包含进边长为 $3$ 的正方形内(内部或边上),可以证明这是最小值。

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

0

所有点从一开始就位于同一坐标。

例如,执行 0 次操作即可让所有点位于同一坐标,因此该输入的答案为 $0$。

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

484373824

数据范围

• 所有输入值均为整数
• $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$