Tour

Time limit1sMemory limit128 MB

Summary

Given points sorted by x-coordinate, compute the shortest bitonic tour that goes strictly left-to-right then strictly right-to-left, using classic O(n^2) DP.

Level: Medium4 of 10
Topics: Dynamic programming, Geometry, Array
Solved: No attempts yet

Problem

John Doe is a skilled pilot who loves to travel. On vacation he rents a small plane and sets off to visit beautiful places. To keep the cost down, he wants the shortest closed tour that connects all of his destinations. Each destination is a point in the plane, and all points have distinct $x$ -coordinates.

John always flies the same kind of route: he starts at the leftmost point, moves strictly from left to right until he reaches the rightmost point, and then moves strictly from right to left back to the starting point.

Given $n$ points in the plane, compute the length of the shortest closed tour that follows John's strategy.

Input

The program input comes from a text file that contains several data sets. Each data set stands for one set of points: first the number of points $n$ , then the $n$ point coordinates in increasing order of the $x$ -coordinate (each point is given by its $x$ and $y$ values). Whitespace may appear freely in the input. All $x$ -coordinates within a data set are distinct, and the input data are correct. Read data sets until the end of the input.

Output

For each set of data, your program should print the result to standard output, starting at the beginning of a line. The result is the tour length, given as a floating-point number with two digits after the decimal point.

Examples3

Example 1

Input

Expected output

6.47
7.89

Example 2
Input
```
2
0 0
3 4
```
Expected output
```
10.00
```
Example 3
Input
```
3
0 0
2 5
5 0
```
Expected output
```
16.22
```