012 - 鉄道建設

時間制限 1 秒 / メモリ制限 256 MB / 得点 12 / x 0 /


TLE
1sec
MLE
256MB
得点
12

$1$ から $N$ までの番号がついた $N$ 個の都市が合併し、ヅイア王国が建国された。ヅイア王国の交通大臣に任命されたあなたは、都市間の街道建設の仕事を与えられた。

あなたは計画を立てるために、各都市を地図上の一点だと考えることにした。そうすると、都市 $i$ は地図上の座標($x_i, y_i$) に存在するとみなせることがわかった。

都市 $u$ と都市 $v$ を結ぶ街道を建設するには、$|x_u - x_v|$と$|y_u - y_v|$のうち大きい方(2つが同じ値ならその値)のコストがかかる。ただし、$|A|$は $A$ の絶対値を表す。相異なる任意の都市の間を1本以上の街道を使って移動できるように建設するとき、かかるコストの合計の最小値を求めたい。

都市の個数と座標を入力とし、街道建設にかかるコストの合計の最小値を求めるプログラムを作成せよ。

入力

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

$N$
$x_1$ $y_1$
$x_2$ $y_2$
...
$x_N$ $y_N$

1行目に、都市の数$N$ ($2 \leq N \leq 10^5$)が与えられる。続く$N$行に、$i$番目の都市の座標$x_i,y_i$ ($0 \leq x_i, y_i \leq 10^9$)が整数で与えられる。ただし、同じ座標をもつ点は与えられない($i≠j$について、$x_i \ne x_j$または$y_i \ne y_j$)。

出力

街道建設にかかるコストの合計の最小値を1行に出力する。

入出力例

入力例1

3
1 2
3 4
10 1

出力例1

9

都市1と都市2を結ぶ街道をコスト2で建設でき、都市2と都市3を結ぶ街道をコスト7で建設できるので、コストの合計は9となり、これが最小である。

入力例2

3
1 2
3 4
3 2

出力例2

4

入力例3

5
7 41
10 0
99 27
71 87
14 25

出力例3

163