問題文

二次元平面上に N 個の都市があり、それぞれ 1 から N までの番号が付けられています。
都市 i の座標は (X_i, Y_i) であり、2 つの都市間を移動するには、直線距離と同じだけ時間がかかります。
すなわち、都市 i から j まで移動するのに、\sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2} 分かかります。

ある都市から出発し、すべての都市を一度ずつ通った後、出発地点に戻るためには最短何分必要でしょうか。

制約

• 2 \leq N \leq 15
• 0 \leq X_i \leq 1000
• 0 \leq Y_i \leq 1000
• 入力はすべて整数

入力例 1

4
0 0
0 1
1 0
1 1

出力例 1

4.000000000000

都市 1 \to 2 \to 4 \to 3 \to 1 というルートを通ると、合計距離が約 4 となります。

入力例 2

7
2 5
2 3
4 1
1 1
7 2
5 3
6 5

出力例 2

18.870481592668

都市 1 \to 2 \to 4 \to 3 \to 5 \to 6 \to 7 \to 1 というルートを通ると、合計距離が約 18.87 となります。