На площині задані координати ~n~ (~4\leqslant n\leqslant 12~) різних вершин.

Знайти довжину найкоротшого замкнутого маршруту, що починається і закінчується в 1-й вершині і відвідує всі інші вершини по одному разу. Дозволяється (якщо так виявляється вигідно) «проїжджати через вершину, не зупиняючись» (див. приклад 1).

Довжина маршруту обчислюється як сума довжин складових його ребер, довжини окремих ребер обчислюються згідно звичайної евклідової метрики, як ~\sqrt{(x_A-x_B)^2+(y_A-y_B)^2}~.

Вхідні дані

Перший рядок містить кількість вершин ~n~ (~4\leqslant n\leqslant 12~). Кожен з наступних ~n~ рядків містить по два розділених пропуском числа з плаваючою точкою – ~x~- та ~y~-координати відповідної вершини.

Результати

Результати повинні містити єдине число (з плаваючою крапкою) – знайдену мінімальну довжину замкнутого маршруту.

Відповідь зараховується, коли абсолютна або відносна похибка (хоча б одна з них) не перевищує ~10^{-9}~.

Приклади

Вхід

4
0 0
2 0.2
7 0.7
5 0.5

Результат

1.40698258695692E+0001

Вхід

5
1 0
4 4
3 2
4 0
1 1

Результат

1.24721359549995E+0001

Примітки

Задача з такими обмеженнями, по ідеї, повинна вирішуватися хоч методом гілок і меж, хоч динамічним програмуванням по підмножинам, хоч самими лише відтинаннями пошуку з поверненням (backtracking), що не намагається оцінювати можливий діапазон довжин ще не збудованої частини шляху.