配点 : $500$ 点

問題文

平面上に、$N$ 個の街があります。$i$ 個目の街は、座標 $(x_i,y_i)$ にあります。同じ座標に、複数の街があるかもしれません。

座標 $(a,b)$ にある街と座標 $(c,d)$ にある街の間に道を造るのには、$min(|a-c|,|b-d|)$ 円かかります。街と街の間以外に、道を造ることはできません。

任意の $2$ つの街の間を、道を何本か通って行き来できるようにするためは、最低で何円必要でしょうか。

制約

• $2 \leq N \leq 10^5$
• $0 \leq x_i,y_i \leq 10^9$
• 入力は全て整数である

入力

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

$N$

$x_1$ $y_1$

$x_2$ $y_2$

:

$x_N$ $y_N$

出力

任意の $2$ つの街の間を道を何本か通って行き来できるようにするためにかかるお金の最小値を出力せよ。

3
1 5
3 9
7 8

3

街 $1$ と $2$ 、街 $2$ と $3$ の間に道を造ると、かかるお金は $2+1=3$ 円になります。

6
8 3
4 9
12 19
18 1
13 5
7 6

8