afaceri

Omul de afaceri Bill este foarte prosper şi are o reţea de magazine în $n$ ţări. Cele $n$ ţări sunt numerotate de la $1$ la $n$ şi reprezentându-le într-un sistem cartezian, fiecare ţară $i$ se învecinează cu ţările $i-1$ şi $i+1$ (cu excepţia ţărilor $1$ şi $n$, care au doar câte un singur vecin). Fiecare ţară $i$ are suprafaţă dreptunghiulară şi are exact $4$ aeroporturi ale căror coordonate sunt numere întregi.
Bill locuieşte în ţara $1$ şi doreşte să se întâlnească cu câte un director economic din fiecare ţară pentru discuţii foarte importante. Cum timpul nu îi permite staţionarea, el va convoca directorii direct la aeroportul unde va ateriza avionul.
Se ştie că domiciliul stabil al lui Bill este în ţara $1$ (ţara cel mai din stânga). El se va deplasa cu avionul parcurgând ţările de la stânga spre dreapta până ce va ajunge în ţara $n$, apoi de la dreapta la stânga până ce va ajunge înapoi în ţara $1$ în aeroportul de unde a pornit, şi în fiecare ţară se va opri câte o singură dată, fie la dus, fie la întoarcere. Pe parcursul călătoriei va alege convenabil aeroporturile astfel încât lungimea drumului parcurs să fie minimă.

Cerință

Să se calculeze lungimea drumului minim. Rezultatul se va tipări ca un număr real.

Date de intrare

Fişierul afaceri.in conţine pe prima linie numărul de ţări $n$. Următoarele $4 \cdot n$ linii conţin câte două numere naturale $x$ şi $y$ separate prin spaţiu, reprezentând câte o coordonată a unui aeroport. Primele $4$ linii conţin coordonatele aeroporturilor din prima ţară, următoarele $4$ linii conţin aeroporturile din a doua ţară, etc.

Date de ieșire

Fişierul afaceri.out va conţine un singur număr real, lungimea drumului minim parcurs de Bill.

Restricții și precizări

• $1 \leq n \leq 300$
• $0 \leq x_i \leq 45 \ 000$
• $0 \leq y_i \leq 3 \ 000$
• Graniţele ţărilor sunt linii orizontale şi verticale, poziţia lor neavând nicio semnificaţie în problema noastră. Aeroporturile sunt strict în interiorul ţărilor, şi nu sunt ordonate după $x$ sau $y$.
• Corectitudinea soluţiei se va verifica cu o precizie de $10^{-3}$.

Exemplu

afaceri.in

4
1 1
1 3
1 10
1 6
2 3
2 1
2 9
2 10
3 4
3 6
3 5
3 7
4 4
4 3
4 2
4 1

afaceri.out

6.472136

Explicație

Avem $4$ ţări.
Aeroporturile au coordonatele:
$1$: $(1, 1), (1, 3), (1, 6), (1, 10)$
$2$: $(2, 1), (2, 3), (2, 9), (2, 10)$
$3$: $(3, 4), (3, 5), (3, 6), (3, 7)$
$4$: $(4, 1), (4, 2), (4, 3), (4, 4)$

Lungimea drumului parcurs este de $6.472136$ şi este desenat în exemplul de mai sus.