004 - 石油 (Oil)

注意

この問題はTLがかなり長めに設定されています。 ジャッジの負荷軽減のため、部分点を狙う方はお手数ですが、N が大きい入力においてはすぐに終了するようなプログラムを書いてもらえると助かります。

問題

二次元平面上に、N 個の油田があります。 i 番目の油田は、座標 (X_i ,Y_i) にあります。

あなたはこの平面上に、石油精製工場を配置したいです。 そして、3 つの油田を選び、それぞれを石油精製工場とパイプラインで繋ぎたいです。 それぞれのパイプラインのコストは、石油精製工場と油田のマンハッタン距離です。 パイプラインのコストの総和を最小化するように、石油精製工場を設置する位置と、繋げる 3 つの油田を選んだ時、 パイプラインのコストの総和がいくつになるかを求めるプログラムを作ってください。 なお、油田の真上に石油精製工場を設置することも可能です。

入力

N
X1 Y1
X2 Y2
:
XN YN

最初の一行には整数 N が与えられる。

続く N 行には、油田の座標が与えられる。

i 行目には、整数 X_i ,Y_i が与えられる。

出力

パイプラインのコストの総和の最小値を出力してください。

制約

全ての入出力ケースについて以下を満たす。

• 3 ≦ N ≦ 10⁶
• 1 ≦ X_i ,Y_i ≦ 10⁹
• 同じ座標に複数の油田はない

小課題

小課題1[15点]

以下の条件を満たす。

• 1 ≦ N ≦ 1000

小課題2[85点]

追加の制約はない。

---

入出力例

入力例1

4
1 1
2 4
3 2
4 3

出力例1

4

解説

座標 (3,3) に石油精製工場を設置し、油田 2 ,3 ,4 をパイプラインでつなぐと、 コストが 4 になり、これが最小です。

入力例2

7
5 7
1 5
2 8
1 1
9 4
7 3
5 2

出力例2

6