AT_abc330_f [ABC330F] Minimize Bounding Square

[problemUrl]: https://atcoder.jp/contests/abc330/tasks/abc330_f $ 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 $ であるものとします。**

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

答えを整数として出力せよ。

### 制約 - 入力は全て整数 - $ 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 $ ### Sample Explanation 1 このケースについて、横を $ x $ 軸、縦を $ y $ 軸として図示したものが以下です。 !\[\](https://img.atcoder.jp/abc330/932178d158b342b9bda6bdc72b439f0e.png) 例えば、図中の矢印に従って $ 4 $ 度の移動を行った後、図中に示した一辺が $ 3 $ の正方形で全ての点を内部または周上に含むことができ、これが最小値であることが示せます。 ### Sample Explanation 2 最初から全ての点が同じ座標に存在します。 例えば操作を $ 0 $ 回行う (即ち、全く行わない) ことにより、全ての点を同じ座標に存在させられるので、この入力に対する答えは $ 0 $ です。