Три зірки

Обмеження: 4 сек., 256 МіБ

Зеник із Марічкою розглядають чисте нічне небо, на якому Марічка побачила \(n\) зірок. Зірки можна зобразити як точки на площині із координатами \((x_i, y_i)\) для усіх \(i\) від 1 до \(n\) включно.

Вона попросила Зеника знайти таку трійку різних зірок \(A\), \(B\) та \(C\), аби мінімізувати суму \(AB + BC\), де \(AB\) — відстань від зірки \(A\) до зірки \(B\), а \(BC\) — відстань від зірки \(B\) до зірки \(C\).

Ваше завдання — знайти цю мінімальну сумарну відстань.

Вхідні дані

У першому рядку задано одне ціле число — кількість зірок, які видно на нічному небі.

У наступних \(n\) рядках задано пари цілих чисел \(x_i\) та \(y_i\) через пробіли — координати зірок на площині.

Вихідні дані

Виведіть одне дійсне число — шукану мінімальну суму відстаней.

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

Обмеження

\(3 \le n \le 1500\),

\(|x_i, y_i| \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 1 4 7 7 11 7 4	9.24264068712

Примітки

Найкраще вибрати третю, другу та четверту точки. Відстань від третьої до другої рівна \(\sqrt{25} = 5\), а від другої до четвертої — \(\sqrt{18}\), отже відповідь рівна \(5 + \sqrt{18} \approx 9.24264068712\).