Star capture

Time limit1sMemory limit512 MB

Summary

Given N integer star positions, find the minimum total length of the rope segments left after the capture steps, where the rope wraps stars in layers.

Level: Medium7 of 10
Topics: Geometry, Sorting
Solved: No attempts yet

Problem

Star uses a rope to capture stars. The capture goes as follows.

Wrap the rope around all the stars to be captured and pull it taut. The rope segments between stars must be taut, and the part of the rope that Star holds must run parallel and must not meet.

Leaving out the stars that touched the rope in step 1, pull both hands closer together while still holding the rope, just far enough that the remaining stars do not touch it.

Pull with all your strength.

Capturing stars can overload the rope until it snaps, so Star wants to reduce the load. Star found that the load gets smaller when the sum of the lengths of the rope segments between stars in step 2 gets smaller.

So the task is to minimize the sum of the lengths of the rope segments between stars. Find how far that sum can be reduced.

Input

The first line contains the number of stars $N$ . $(2 \leq N \leq 100\,000)$

From the second line on, $N$ lines each give the position $x_i, y_i$ of one star, separated by a space, one star per line. $x_i$ and $y_i$ are integers. No two or more stars share the same position. $(-3\,000\,000 \leq x_i, y_i \leq 3\,000\,000)$

Output

Print the minimum possible sum of the lengths of the rope segments between stars.

An absolute or relative error of up to $10^{-6}$ is allowed.

Examples3

Example 1

Input

Expected output

18.109958183491

Example 2
Input
```
4
-1 -1
-1 1
1 -1
1 1
```
Expected output
```
4.000000000000
```

Example 3

Input

Expected output

5.656854249492