Road Construction and City Alliance

A country has \(n\) cities with no roads connecting any two of them, which makes transportation difficult. To solve this problem, the government has decided to build roads, and the task is shared by all the cities.

The construction is carried out in several rounds. In each round, every city (or, in later rounds, every city alliance) chooses another city (or alliance) that is the closest to it and applies for constructing a road to that city. The government then approves these applications according to the following rules:

1. If two or more cities apply to build the same road, they will build it together.
2. If three or more cities apply for roads that form a cycle (for example, city A applies for road \(AB\), city B for road \(BC\), and city C for road \(CA\)), the government will cancel the application for the shortest road in that cycle.
3. All other applications are approved.

After one round of construction, some cities may become directly or indirectly connected by the newly built roads. These interconnected cities form a "city alliance". In subsequent rounds, each city alliance is treated as a single city.

When all the cities are connected into a single alliance, the construction work is complete. Your task is to calculate the total length of the roads that will be built.

Note: The process described above is equivalent to constructing a Minimum Spanning Tree (MST) over all the cities, where the weight between two cities is the Euclidean distance between them. Thus, the answer is the sum of the weights of the MST.

inputFormat

The first line contains an integer \(n\) (\(2 \le n \le 1000\)) — the number of cities. Each of the following \(n\) lines contains two integers \(x\) and \(y\) (\(-10^4 \le x, y \le 10^4\)), representing the coordinates of one city.

outputFormat

Output a single number representing the total length of the roads that will be built. Your answer is considered correct if its absolute or relative error does not exceed \(10^{-3}\).

sample

4
0 0
0 1
1 0
1 1

3.000