Као и обично, овај задатак се односи на једну чудну ситуацију – потребно је испланирати испоруке за свемирског поштара у 2318. години. У пошти, која се налази на планети са координатама \((0,0)\), се налази \(N\) пакета које треба доставити на различите планете, чије су координате дате (свемир је дводимензионалан, координате \(i\)-те планете су \((X_i,Y_i)\)).

Свемирски поштар се мора придржавати следећих правила:

• Пакети се разносе два по два - када крене из поште, поштар мора да оде до једне планете и испоручи пакет, затим од ње директно до друге, и након тога да се врати у пошту (где ће преузети наредна два пакета, ако их још има).
• Између планета (укљјучујући и планету на којој је пошта) се мора кретати правом линијом (најкраћим путем).
• Путања којом се поштар креће (изломљена линија која спаја планете) не сме сећи саму себе.

Ваш задатак је да пронађете пут који поштује ова три правила, такав да му је укупна дужина минимална.

Опис улаза

У првој линији стандардног улаза налази се један природан број \(N\) - број планета на које треба однети пакете. У наредних \(N\) линија се налазе по два броја \(X_i\) и \(Y_i\) - координате \(i\)-те планете.

Опис излаза

У јединој линији исписати један реалан број - укупну дужину најкраћег пута који поштује сва правила. Решење ће бити прихваћено ако се разликује од тачног за највише \(10^{-6}\) (као релативна или апсолутна грешка).

Пример 1

Улаз

4
-1 1
-1 4
1 1
1 4

Излаз

17.07463838

Објашњење примера

Најкраћи пут који задовољава сва три правила је следећи: \((0,0) \rightarrow (-1,1) \rightarrow (-1,4) \rightarrow (0,0) \rightarrow (1, 4) \rightarrow (1, 1) \rightarrow (0,0)\). Кад не би било трећег правила, поштар би могао да прво достави пакете првој и трећој, а затим другој и четвртој планети, али та путања није дозвољена јер се путеви од поште до друге планете и од прве до треће секу.

Ограничења

• \(N\) је парно.
• За све \(i\), \(-10^6 \leq X_i, Y_i \leq 10^6\).
• Ниједне две планете (укључујући пошту) се не налазе на истој позицији.
• Ниједне три планете (укључујући пошту) нису колинеарне.

Тест примери су подељени у пет дисјунктних група:

• У тест примерима вредним 20 поена: \(N \leq 8\) и за све \(i\) важи \(Y_i > 0\).
• У тест примерима вредним 20 поена: \(N \leq 100\) и за све \(i\) важи \(Y_i > 0\).
• У тест примерима вредним 20 поена: \(N \leq 500\) и за све \(i\) важи \(Y_i > 0\).
• У тест примерима вредним 20 поена: \(N \leq 100\).
• У тест примерима вредним 20 поена: \(N \leq 500\).