7. Ideme robiť kampaň

Voľby v Krajine Samých Politikov sú už za rohom.

Treba byť akční! Však ak s tým nič neurobíme, tí politici z opozície - Fakt Kool Strana - nebodaj získajú demokratickú väčšinu, postavia vládu, a začnú plniť svoje predvolebné sľuby! Koalícia Mnohých Strán tomu musí nejako zabrániť.

KMS sa teda rozhodla zorganizovať predvolebnú kampaň, na ktorej vycestujú z hlavného mesta a navštívia všetky okresné mestá, po čom sa slávnostne vrátia do hlavného mesta v deň volieb.

Mohli síce vyrátať najkratšiu cestu ktorú by museli prejsť, bol by to však problém. Ak by totiž navštívili okresné mestá v tak špecifickom poradí, žurnalisti z časopisu Zuby a Vlasy by si to určite vysvetlili tak, že na okresoch ktoré KMS navštívi posledné im nezáleží, a stratili by v nich voličov.

Keďže KMS nemá hlavného vedúceho ktorý by vedel takéto obvinenia verejne poprieť, rozhodlo sa KMS pre inú stratégiu - spravia okruhovú cestu krajinou. Začnú v hlavnom meste, ktoré je najzápadnejšie okresové mesto. Potom sa vydajú na východ, pričom ponavštivujú niektoré mestá, až kým neprídu do najvýchodnejšieho z nich. Vtedy spravia otočku a vydajú sa na západ, pričom navštívia všetky mestá ktoré vynechali v opačnom smere, až kým nakoniec neprídu naspäť do hlavného mesta.

Pomôžte KMSákom zrátať, koľko najmenej kilometrov musia prejsť, aby mohli takto zorganizovať svoju predvolebnú kampaň a poraziť FKS!

Úloha

Každé mesto si vieme predstaviť ako bod v rovine.

KMS začína v najzápadnejšom meste, a potom sa vydá na východ k najvýchodnejšiemu mestu. Po ceste môže navštíviť niektoré mestá, tie však musia mať rastúcu zemepisnú dĺžku (\(x\)-ovú súradnicu).

Po príchode do najvýchodnejšieho mesta sa KMS otočí a vydá na západ, pričom v klesajúcom poradí zemepisnej dĺžky navštívi všetky mestá, ktoré KMSáci nenavštívili počas kampaňovania na východ.

Akú najmenšiu vzdialenosť musia prejsť?

Formát vstupu

V prvom riadku vstupu je číslo \(n\) – počet miest v KSP. Každý z nasledovných \(n\) riadkov obsahuje dve čísla \(x_i y_i\): súradnice jedného mesta. Tie sú kladné a nepresahujú milión. Body budú udávané v rastúcom poradí zemepisnej dĺžky (teda žiadne mestá nemajú rovnakú zemepisnú dĺžku, a prvé mesto na vstupe je hlavné mesto).

Formát výstupu

Vypíšte najmenšiu vzdialenosť ktorú KMSáci musia prejsť aby zvládli svoju okruhovú predvolebnú kampaň. Dĺžku ich cesty meriame Euklidovsky.

Vypíšte dostatočne veľa desatinných miest. Vaša odpoveď bude uznaná, ak sa bude od našej líšiť v absolutnéj alebo relatívnej hodnote najviac \(10^{-6}\).

Hodnotenie

Čím väčšia sada, tým väčšie \(n\), zhora ohraničené postupne:

1. Počtom prstov na mojich rukách a nohách

2. Počtom dní v letných prázdninách

3. Počtom dní v orbite Venuše

4. Rokom v ktorom Krištof Kolumbus objavil Ameriku

\(n\) nikdy nie je menšie ako počet trpaslíkov v rozprávke o Snehulienke mínus päť.

Príklady

Input:

5
1 3
2 1
3 4
4 4
5 2

Output:

10.870481593

Input:

10
4 1
13 4
21 3
25 9
28 10
42 1
43 2
50 4
67 10
68 9

Output:

131.651455225