Bitonic Traveling Salesman Problem (Bitonic TSP)

For given $N$ points in the 2D Euclidean plane, find the distance of the shortest tour that meets the following criteria:

• Visit the points according to the following steps:
  1. It starts from the leftmost point (starting point), goes strictly from left to right, and then visits the rightmost point (turn-around point).
  2. Then it starts from the turn-around point, goes strictly from right to left, and then back to the starting point.
• Through the processes 1. 2., the tour must visit each point at least once.

Input

The input data is given in the following format:

$N$
$x_1$ $y_1$
$x_2$ $y_2$
...
$x_N$ $y_N$

Constraints

• $2 \leq N \leq 1000$
• $-1000 \leq x_i, y_i \leq 1000$
• $x_i$ differ from each other
• The given points are already sorted by x-coordinates

Output

Print the distance of the shortest tour in a line. The output should not have an error greater than 0.0001.

Sample Input 1

3
0 0
1 1
2 0

Sample Output 1

4.82842712

Sample Input 2

4
0 1
1 2
2 0
3 1

Sample Output 2

7.30056308

Sample Input 3

5
0 0
1 2
2 1
3 2
4 0

Sample Output 3

10.94427191

---