Score : $525$ points

问题描述

在 $xy$ 平面上有 $N$ 个标记为 $1, 2, \dots, 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)$。
• 允许多个点位于相同的坐标上。注意输入可能已经存在多个位于相同坐标的点。

所有操作结束后，画出一个包含全部 $N$ 个点在内部或边界上的正方形，每条边与 $x$ 轴或 $y$ 轴平行。

找出这个正方形边长的最小可能值。由于所有点始终位于格点上，可以证明这个值总是整数。

特别地，如果所有点都可以移动到同一坐标位置，则答案被认为是 $0$。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ points labeled $1, 2, \dots, N$ on the $xy$-plane. Point $i$ is located at coordinates $(X_i, Y_i)$.
You can perform the following operation between $0$ and $K$ times, inclusive.

• First, choose one of the $N$ points. Let $k$ be the selected point, and assume it is currently at $(x, y)$.
• Next, choose and execute one of the following four actions:
  • Move point $k$ along the $x$-axis by $+1$. The coordinates of point $k$ become $(x+1, y)$.
  • Move point $k$ along the $x$-axis by $-1$. The coordinates of point $k$ become $(x-1, y)$.
  • Move point $k$ along the $y$-axis by $+1$. The coordinates of point $k$ become $(x, y+1)$.
  • Move point $k$ along the $y$-axis by $-1$. The coordinates of point $k$ become $(x, y-1)$.
• It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.

After all your operations, draw one square that includes all the $N$ points inside or on the circumference, with each side parallel to the $x$- or $y$-axis.
Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points.

In particular, if all points can be made to exist at the same coordinates, the answer is considered to be $0$.

Constraints

• All input values are integers.
• $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$

Input

Input is given from Standard Input in the following format:

$N$ $K$

$X_1$ $Y_1$

$X_2$ $Y_2$

$\vdots$

$X_N$ $Y_N$

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

3

The figure below illustrates this case with the horizontal $x$-axis and the vertical $y$-axis.

For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of $3$, and this can be shown to be the minimum value.

Sample Input 2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0

All points already exist at the same coordinates from the beginning.
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is $0$.

Sample Input 3

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

Sample Output 3

484373824

update @ 2024/3/10 01:14:41