H - 空港 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

Problem Statement

すぬけ君は、空港を N 個持っている。i 番目の空港の座標は (x_i, y_i) である。すぬけ君は、あまり近い空港の間に飛行機を飛ばしても意味がないので、マンハッタン距離 ((x_1, y_1) と (x_2, y_2) のマンハッタン距離は |x_1 - x_2| + |y_1 - y_2|) が X 以上である全ての空港のペアの間に飛行機を飛ばすことにした。どの空港からどの空港へも飛行機だけを使っていけるようになる最大の X を求めよ。

Constraints

  • 2 \leq N \leq 100000
  • 0 \leq x_i, y_i \leq 10^9
  • 二つの空港が同じ座標にあることはない。

Input Format

入力は以下の形式で標準入力から与えられる。 
N
x_1 y_1
:
x_N y_N

Output Format

答えを一行に出力せよ。

Sample Input 1

6
1 7
8 5
6 3
10 3
5 2
6 10

Sample Output 1

9