配点 : $500$ 点

問題文

二次元平面上に $N$ 個の点があり、$i$ 番目の点の座標は $(x_i,y_i)$ です。 同じ座標に複数の点があることもあります。 異なる二点間のマンハッタン距離として考えられる最大の値はいくつでしょうか。

ただし、二点 $(x_i,y_i)$ と $(x_j,y_j)$ のマンハッタン距離は $|x_i-x_j|+|y_i-y_j|$ のことをいいます。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq x_i,y_i \leq 10^9$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$x_1$ $y_1$

$x_2$ $y_2$

$:$

$x_N$ $y_N$

出力

答えを出力せよ。

3
1 1
2 4
3 2

4

$1$ 番目の点と $2$ 番目の点のマンハッタン距離は $|1-2|+|1-4|=4$ で、これが最大です。

2
1 1
1 1

0