Farmer John a installé une nouvelle machine à traire sophistiquée dans son étable, mais elle consomme tant d'électricité qu'elle provoque parfois une coupure ! Cela arrive si souvent que Bessie a mémorisé le plan de l'étable pour trouver plus facilement la sortie dans le noir. Elle s'interroge toutefois sur l'effet des coupures sur sa capacité à sortir vite, notamment sur la distance supplémentaire à parcourir dans le noir.

L'étable est un polygone simple (sans auto-intersection), de sommets entiers $(x_1, y_1) \ldots (x_n, y_n)$ énumérés dans le sens horaire. Ses côtés alternent entre horizontaux (parallèles à l'axe $x$) et verticaux (à l'axe $y$) ; le premier peut être de l'un ou l'autre type. La sortie est en $(x_1, y_1)$. Bessie commence dans l'étable au sommet $(x_i, y_i)$ avec $i > 1$. Elle ne peut marcher que le long du périmètre, dans un sens ou l'autre, et veut minimiser la distance à la sortie. Avec la lumière, il suffit de choisir le sens le plus court depuis sa position.

Un jour, les lumières s'éteignent : Bessie panique et oublie son sommet. Elle se souvient pourtant du plan exact et peut retrouver sa position en marchant et en touchant. À chaque sommet, y compris le sommet initial, elle perçoit l'angle intérieur exact et sait si c'est la sortie. Après avoir parcouru un côté entier, elle en connaît la longueur exacte. Sa stratégie est de suivre le périmètre dans le sens horaire jusqu'à avoir senti assez d'angles et de côtés pour déduire son sommet actuel. Elle peut alors emprunter le trajet restant le plus court vers la sortie, en continuant dans le sens horaire ou en changeant de sens.

Déterminez l'augmentation maximale de sa distance dans le noir par rapport à l'étable éclairée, dans le pire cas parmi tous les sommets de départ.

Entrée

La première ligne contient $N$ ($4 \leq N \leq 200$). Les $N$ lignes suivantes donnent chacune deux entiers, décrivant les sommets $(x_i, y_i)$ dans le sens horaire. Ces entiers sont dans $-100,000 \ldots 100,000$.

Sortie

Affichez l'augmentation maximale de distance pour le pire sommet initial avec la stratégie décrite.

Exemples

Entrée 1

4
0 0
0 10
1 10
1 0

Sortie 1

2

Remarque

Dans l'exemple, Bessie sent un angle initial de 90 degrés mais ne distingue pas les sommets 2, 3 et 4. Après un côté parcouru dans le sens horaire, elle atteint la sortie ou identifie sa position grâce à la longueur du côté. Les distances sont :

Depuis le sommet 2 : 12 unités dans le noir (1 jusqu'au sommet 3, puis 11 jusqu'à la sortie), contre seulement 10 avec la lumière. Le supplément est 2.

Depuis le sommet 3 : 11 unités dans les deux cas.

Depuis le sommet 4 : 1 unité dans les deux cas.

La pire différence vaut donc $12 - 10 = 2$. Sa stratégie garantit ainsi, quel que soit le départ, au plus 2 unités supplémentaires dans le noir par rapport à la lumière.

Auteur du problème : Brian Dean