バイトニック巡回セールスマン (Bitonic TSP)

２次元のユークリッド空間上の $N$ 個の点について、以下の条件を満たす最短経路の距離を求めてください。

• $x$ 座標が最小の点を始点、$x$ 座標が最大の点を折り返し点とし、次の手順で点を訪問する。
  1. 始点を出発し、$x$ が増加する方向へ進み、折り返し点を訪れる。
  2. 折り返し点を出発し、$x$ が減少する方向へ進み、始点へ戻る。
• 1. 2. を通して各点を少なくとも1度訪れる。

Input

入力は以下の形式で与えられる。

$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$ は互いに異なる
• 座標は $x_i$ が小さい順に与えられる

Output

最短経路の距離を１行に出力する。出力値は 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

---