Road Construction

The Zuia Kingdom has finally emerged through annexation of $N$ cities, which are identified by index from $1$ to $N$. You are appointed the Minister of Transport of the newly born kingdom to construct the inter-city road network.

To simplify the conceptual design planning, you opted to consider each city as a point on the map, so that the $i$-th city can be represented by an coordinate ($x_i, y_i$).

The cost of road construction connecting $u$-th and $v$-th cities is equal to the distance $|x_u - x_v|$ or $|y_u - y_v|$, whichever the larger. The notation $|A|$ represents the absolute value of $A$. The object here is to explore the minimum cost required to construct the road network in such a way that people can move between different cities along one or more roads.

Make a program to calculate the minimum of total road construction cost from the number of cities and their coordinates.

Input

The input is given in the following format.

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

The first line provides the number of cities $N$ ($2 \leq N \leq 10^5$). Each of the subsequent $N$ lines provides the coordinate of the $i$-th city $x_i, y_i$ ($0 \leq x_i, y_i \leq 10^9$) as integers. Note that none of these coordinates coincides if: $i \ne j$, then $x_i \ne x_j$ or $y_i \ne y_j$.

Output

Output the minimum road construction cost.

Examples

Input

3 1 2 3 4 10 1

Output

9

Input

3 1 2 3 4 3 2

Output

4

Input

5 7 41 10 0 99 27 71 87 14 25

Output

163

inputFormat

Input

The input is given in the following format.

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

The first line provides the number of cities $N$ ($2 \leq N \leq 10^5$). Each of the subsequent $N$ lines provides the coordinate of the $i$-th city $x_i, y_i$ ($0 \leq x_i, y_i \leq 10^9$) as integers. Note that none of these coordinates coincides if: $i \ne j$, then $x_i \ne x_j$ or $y_i \ne y_j$.

outputFormat

Output

Output the minimum road construction cost.

Examples

Input

3 1 2 3 4 10 1

Output

9

Input

3 1 2 3 4 3 2

Output

4

Input

5 7 41 10 0 99 27 71 87 14 25

Output

163

样例

3
1 2
3 4
3 2

4