Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 64M

Problem type

King Eric is the ruler of a large country composed of N (2 \leq N \leq 2\cdot10^5) towns. Unfortunately for him, the infrastructure of his country is not doing so well. The roads have all crumbled into nothingness, hindering economic activity and leading to civil unrest. Eric has turned to you, an up and coming computer scientist with a vast understanding of graph theory to come up with a roadwork plan.

You study the map of the nation. Each town can be seen as a point on the coordinate grid, the i^{th} town located at the point (x_i,y_i) (0\le x_i \le 10^9,0\le y_i \le 10^9). Building a road between two towns comes with a cost. If the two towns are at the coordinates (a,b) and (c,d), then the cost of construction is \min(|a-c|,|b-d|).

King Eric wants to save as much money as possible. He does not require a road between every pair of towns. Rather, he just wants it to be possible to start at any town and reach any other town by traversing some path of roads. What is the minimum total cost of a roadwork plan?

Input Specification

The first line contains one integer N, the number of towns.

The next N lines each contain two integers, x_i and y_i, the coordinates of the i^{th} town.

Output Specification

Output the cost needed to build roads optimally.

Sample Input

1 2
5 1
3 4

Sample Output


Sample Explanation

Build a road between towns 1 and 2 and towns 1 and 3.


There are no comments at the moment.