Farmer John hat eine schicke neue Melkmaschine im Stall installiert, aber sie verbraucht so viel Strom, dass gelegentlich der Strom ausfällt! Das passiert so oft, dass Bessie den Stallplan auswendig kennt, um im Dunkeln leichter den Ausgang zu finden. Sie interessiert sich jedoch dafür, wie Ausfälle das schnelle Verlassen beeinflussen, etwa wie viel weiter sie im Dunkeln laufen muss.

Der Stall ist ein einfaches (nicht selbstschneidendes) Polygon mit ganzzahligen Eckpunkten $(x_1, y_1) \ldots (x_n, y_n)$ im Uhrzeigersinn. Die Kanten wechseln zwischen horizontal (parallel zur $x$-Achse) und vertikal (zur $y$-Achse); die erste darf beliebig sein. Der Ausgang liegt bei $(x_1, y_1)$. Bessie beginnt im Stall an einer Ecke $(x_i, y_i)$ mit $i > 1$. Sie darf nur am Rand im oder gegen den Uhrzeigersinn gehen und will den kürzesten Weg zum Ausgang. Bei Licht ist das einfach: Sie wählt die kürzere Richtung von ihrer aktuellen Position.

Eines Tages geht das Licht aus und Bessie vergisst in Panik ihre Ecke. Sie kennt den genauen Plan weiterhin und kann durch Gehen und Tasten ihre Position ermitteln. An jeder Ecke, auch der Anfangsecke, fühlt sie den genauen Innenwinkel und erkennt, ob dies der Ausgang ist. Nach dem vollständigen Gehen einer Kante kennt sie deren genaue Länge. Ihre Strategie: im Uhrzeigersinn gehen, bis sie genügend Winkel und Kanten ertastet hat, um die aktuelle Ecke zu bestimmen. Dann nimmt sie den kürzesten verbleibenden Weg zum Ausgang, indem sie im Uhrzeigersinn weitergeht oder die Richtung umkehrt.

Bestimme die größte zusätzliche Weglänge im Dunkeln gegenüber dem beleuchteten Stall im schlimmsten Fall über alle möglichen Anfangsecken.

Eingabe

Die erste Zeile enthält $N$ ($4 \leq N \leq 200$). Die nächsten $N$ Zeilen enthalten je zwei ganze Zahlen für $(x_i, y_i)$ im Uhrzeigersinn. Sie liegen im Bereich $-100,000 \ldots 100,000$.

Ausgabe

Gib die größte zusätzliche Weglänge bei der schlechtesten Anfangsposition unter der beschriebenen Strategie aus.

Beispiele

Eingabe 1

4
0 0
0 10
1 10
1 0

Ausgabe 1

2

Hinweis

Im Beispiel fühlt Bessie anfangs einen 90-Grad-Winkel, kann aber die Ecken 2, 3 und 4 nicht unterscheiden. Nach einer ganzen Kante im Uhrzeigersinn erreicht sie den Ausgang oder bestimmt anhand der Länge ihre Position eindeutig. Die Strecken sind:

Von Ecke 2: im Dunkeln 12 Einheiten (1 zu Ecke 3, dann 11 weiter zum Ausgang), bei Licht nur 10. Der Zusatz beträgt 2.

Von Ecke 3: in beiden Fällen 11 Einheiten.

Von Ecke 4: in beiden Fällen 1 Einheit.

Die schlimmste Differenz ist somit $12 - 10 = 2$. Die Strategie garantiert unabhängig vom Anfang im Dunkeln höchstens 2 Einheiten mehr als bei Licht.

Aufgabenautor: Brian Dean