Farmer John zainstalował w oborze nową, wymyślną dojarkę, lecz pobiera ona tyle prądu, że czasem powoduje jego zanik! Dzieje się to tak często, że Bessie zapamiętała plan obory, by łatwiej znaleźć wyjście w ciemności. Interesuje ją jednak wpływ awarii na szybkość wyjścia, na przykład o ile dalej musi iść po ciemku.

Obora jest prostym (bez samoprzecięć) wielokątem z całkowitymi wierzchołkami $(x_1, y_1) \ldots (x_n, y_n)$ podanymi zgodnie z ruchem wskazówek zegara. Boki na zmianę są poziome (równoległe do osi $x$) i pionowe (do osi $y$); pierwszy może być dowolnego rodzaju. Wyjście jest w $(x_1, y_1)$. Bessie zaczyna w oborze w wierzchołku $(x_i, y_i)$ przy $i > 1$. Może iść tylko po obwodzie, zgodnie lub przeciwnie do wskazówek zegara, i chce minimalnej drogi do wyjścia. Przy świetle wystarczy wybrać krótszy kierunek z obecnego miejsca.

Pewnego dnia światła gasną i Bessie w panice zapomina swój wierzchołek. Nadal pamięta dokładny plan i może ustalić pozycję, idąc i dotykając. W każdym wierzchołku, również początkowym, czuje dokładny kąt wewnętrzny i wie, czy to wyjście. Po przejściu całego boku zna jego dokładną długość. Jej strategia to iść zgodnie ze wskazówkami zegara, aż pozna dość kątów i boków, by określić obecny wierzchołek. Potem idzie najkrótszą pozostałą drogą do wyjścia, kontynuując w tym kierunku lub odwracając go.

Wyznacz największy przyrost drogi w ciemności względem oświetlonej obory w najgorszym przypadku spośród wszystkich początkowych wierzchołków.

Wejście

Pierwszy wiersz zawiera $N$ ($4 \leq N \leq 200$). Każdy z kolejnych $N$ wierszy zawiera dwie liczby całkowite, wierzchołki $(x_i, y_i)$ zgodnie ze wskazówkami zegara. Liczby są z zakresu $-100,000 \ldots 100,000$.

Wyjście

Wypisz największy przyrost drogi dla najgorszej pozycji początkowej przy opisanej strategii.

Przykład

Wejście 1

4
0 0
0 10
1 10
1 0

Wyjście 1

2

Uwagi

W przykładzie Bessie czuje początkowo kąt 90 stopni, lecz nie odróżnia wierzchołków 2, 3 i 4. Po przejściu boku zgodnie ze wskazówkami zegara dociera do wyjścia lub jednoznacznie określa pozycję z długości boku. Drogi wynoszą:

Z wierzchołka 2: 12 jednostek w ciemności (1 do wierzchołka 3, potem 11 do wyjścia), a przy świetle tylko 10. Nadmiar wynosi 2.

Z wierzchołka 3: 11 jednostek w obu przypadkach.

Z wierzchołka 4: 1 jednostka w obu przypadkach.

Najgorsza różnica to $12 - 10 = 2$. Strategia gwarantuje zatem, niezależnie od początku, najwyżej 2 dodatkowe jednostki drogi w ciemności względem światła.

Autor zadania: Brian Dean