Problem D
Flygildi

Image by Richard Unten

The webstore Amazon has in the last few years been planning a new way to deliver packages to customers using drones¹. When the new delivery system is up and running customers will be able to get their deliveries within just a few hours rather than a few days.

Each drone gets a few packages to deliver at a time, and each package has a certain destination it needs to be delivered to. The area the drones fly over is modeled as a two dimensional coordinate system, where the Amazon warehouse is located at $(0,0)$ and package number $i$ needs to be delivered to the coordinates $(x_i,y_i)$. The drone thus needs to fly from the warehouse to all delivery locations and then back to the warehouse when the deliveries have been made.

It’s clear that the order in which the drone visits the delivery locations matters, since a bad order could mean that the drone takes a far longer route to drop off the packages than is necessary. Amazon has hired you to solve this problem. Given the number of packages $N$ that need to be delivered and the delivery locations, what’s the shortest path that the drone needs to travel to leave the warehouse, drop off the packages at their locations in some order, and then return to the warehouse. You may assume the drone can fly in a straight line between any two locations without worrying about collisions.

Input

The first line contains the integer $N$ denoting the number of packages that need to be delivered. Then there are $N$ lines, one for each package. On the $i$-th line there will be two integers $-10\, 000\leq x_i,y_i \leq 10\, 000$, where $(x_i,y_i)$ denotes the delivery location of the $i$-th package.

Output

One line containing the shortest path the drone can take. The answer is considered correct if its absolute or relative error from the correct answer is at most $10^{-6}$. This means that it doesn’t matter how many digits the answer contains as long as its accurate enough.

Explanation of Sample Inputs

In the first sample there are only two packages. In this case it does not matter in what order they are delivered. If the drone flies in a direct line each time then the length will be $1 + \sqrt{2} + 1 \approx 3.414214$.

Figure 1: Image showing the third sample.

The third sample is shown in the image above. Here the shortest path is to drop the packages off in the order $1$, $2$, $4$, $3$ and that gives a distance just shy of $40$.

Scoring

The solution will be tested on differently hard input data and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

2
0 1
1 0

3.4142135624

3
0 1
0 2
0 4

8.0000000000

4
0 10
2 12
10 0
12 2

39.7989898732