Description

It was the first anniversary of TN's coronation. After one year's reconstruction, towns and cities were gradually rebuilt. There emerged a call for a complete traffic system. Among all choices to solve the problem, TN considered the construction of an expressway system the best one. He followed his old way in planning - to build the fewest number of expressways that would connect all the cities.

Though it was a similar case to what had previously been done, differences existed. The most significant one was that building expressways was costly. TN wanted to minimize the cost to achieve the goal. It was known that the cost of building an expressway between two cities was proportional to the distance between the cities. What was more, the expressways were straight and no two expressways could cross each other due to technical limitations. Now TN was holding a map of his kingdom, fallen deep in thinking. How should he make the plan?

Input

The input consists of a single test case. The first line of input contains a positive integer N not exceeding 10⁵ which is the number of cities in the kingdom. Then N lines follow. Each line contains a pair of non-negative integers within 50,000, giving in that order the x- and y-coordinates of a city in the Cartesian coordinate system. The distance between two cities was measured in the L₂-metric, which means for two cities located at (x₁, y₁) and (x₂, y₂), the distance between them was

Output

Your solution should output a single number rounded to four decimal places which is the minimum cost of building the expressways under the assumption that building an expressway covering one unit of distance required exactly one unit of cost.

2
0 0
1 1

1.4142

Hint

It is recommended that your solution uses standard C I/O interface to achieve better efficiency and avoid unpredictable behaviours.

Source

POJ Monthly--2006.04.28, frkstyc@PKU_RPWT