問題文

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

これからあなたは二次元平面上の好きな場所を 1 つ選び、発電所を建設します。

発電所の不便さを、発電所から各工場までのマンハッタン距離の総和と定義するとき、不便さとしてありうる最小の値を求めてください。なお、この問題の制約下で答えは整数となることが証明できます。

制約

• 1 \leq N \leq 10^5
• -10^9 \leq X_i, Y_i \leq 10^9
• 入力は全て整数

入力例 1

2
-1 2
1 1

出力例 1

3

発電所を (0, 1) に建設することで、発電所から各工場までのマンハッタン距離は次のようになります。

• 工場 1 ： |-1 - 0| + |2 - 1| = 2
• 工場 2 ： |1 - 0| + |1 - 1| = 1

このときの不便さは 2 + 1 = 3 であり、不便さを 3 より小さくすることはできないため 3 を出力します。

入力例 2

2
1 0
0 1

出力例 2

2

発電所を (1, 0) に建設することで不便さの最小値 2 を達成できます。

また、発電所を (0.5, 0.5) や (0, 1) に建設した場合も同様に不便さは 2 となります。

入力例 3

5
2 5
2 5
-3 4
-4 -8
6 -2

出力例 3

35

同じ座標に複数の工場が存在することもあります。

入力例 4

4
1000000000 1000000000
-1000000000 1000000000
-1000000000 -1000000000
1000000000 -1000000000

出力例 4

8000000000