001 - 博覧会 (Exposition)

問題

　JOI 市では，とある大規模な博覧会を開催することになった．
　今回の博覧会には 2 つのテーマがあり，JOI 市にある N 個の展示施設でそれぞれ，2 つのテーマのうちどちらか一方に沿った展示を行う予定である．
　施設の位置は平面座標 (x, y) で表される．位置 (x, y) にある施設から (x′, y′) にある施設まで移動するためには，|x - x′| + |y − y′| だけの時間がかかる (整数 a に対して, |a| で a の絶対値を表す)．同一テーマ内での統一感を出すため，および一方のテーマのみに関心を持つ人に不便を感じさせないために，同一のテーマで展示を行ってい る 2 つの施設の間の移動時間がなるべく短くなるようにテーマを割りふりたい．すべての展示施設に同じテーマを割りふらない限り, どのようにテーマを割りふってもよい.
　同一のテーマで展示を行っている 2 つの施設の間の移動時間の最大値を M とする. N 個の展示施設の位置が与えられたとき，M の最小値を求めるプログラムを作成せよ．

入力

　入力の 1 行目には, 施設の個数 N(3 ≤ N ≤ 100000 = 10⁵) が書かれている．入力の i + 1 行目 (1 ≤ i ≤ N) には，各施設の座標を表す 2 つの整数 x_i, y_i (|x_i| ≤ 100000 = 10⁵, |y_i| ≤ 100000 = 10⁵) が空白区切りで書かれている．これは，i 個目の施設の座標が (x_i, y_i) であることを表す．同一の座標に 2 つ以上の施設が存在することはない．
　採点用データのうち，配点の 40% 分については, N ≤ 2000 である.

出力

　出力は 1 行のみからなる．同一のテーマで展示を行っている 2 つの施設間の移動時間の最大値 M の最小値を出力せよ．

入出力例

入力例 1

5
0 0
1 0
-1 -2
0 1
-1 1

出力例 1

3

　この場合，たとえば座標 (0, 0), (1, 0), (0, 1) にある施設に一方のテーマを，(−1, −2), (−1, 1) にある施設にもう一方のテーマを割りふると，同一のテーマで展示を行う 2 つの施設間の移動時間はすべて 3 以下になる．移動時間をすべて 2 以下にすることはできないので，3 を出力する．