/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
xy 平面上に N 個の点 1,2,\dots,N があります。このうち点 i は座標 (X_i,Y_i) にあります。
あなたは、以下の操作を 0 回以上 K 回以下行うことができます。
- まず、 N 点の中からひとつを選択する。選ばれた点を k とし、この点が現在 (x,y) にあるものとする。
- 次に、以下の 4 つからひとつを選択し、実行する。
- 点 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 軸として図示したものが以下です。
例えば、図中の矢印に従って 4 度の移動を行った後、図中に示した一辺が 3 の正方形で全ての点を内部または周上に含むことができ、これが最小値であることが示せます。
入力例 2
4 400000000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 2
0
最初から全ての点が同じ座標に存在します。
例えば操作を 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
Score : 525 points
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