King Eric is the ruler of a large country composed of 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 town located at the point . Building a road between two towns comes with a cost. If the two towns are at the coordinates and , then the cost of construction is .
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 , the number of towns.
The next lines each contain two integers, and , the coordinates of the town.
Output Specification
Output the cost needed to build roads optimally.
Sample Input
3
1 2
5 1
3 4
Sample Output
3
Sample Explanation
Build a road between towns and and towns and .
Comments