El Granjero Juan ha instalado una nueva máquina de ordeñar bonita en su establo, pero demanda tanta orriente eléctrica que ocasionalmente causa que la corriente eléctrica se vaya. Esto pasa tan frecuentemente que Bessie ha memorizado un mapa del establo, haciendo más fácil a ella encontrar la salida al establo en la oscuridad. Ella tiene curiosidad acerca del impacto de la pérdida de energía eléctrica y su habilidad para salir fácilmente del establo. Por ejemplo, ella se pregunta cuánto más necesitaría caminar para encontrar la salida en la oscuridad.

El establo está descrito por un polígono simple (no se auto-interseca) con vértices enteros ~(x_1,y_1)...(x_n,y_n)~ mostrados en orden horario. Sus lados se alternan entre horizontales (paralelos al eje x) y verticales (paralelos al eje y); el primer lado puede ser de cualquier tipo. La salida está ubicada en ~(x_1,y_1)~. Bessie comienza dentro del establo ubicada en algún vértice ~(x_i,y_i)~ con ~i > 1~. Ella puede caminar únicamente alrededor del perímetro del establo, en sentido horario o anti-horario. Su objetivo es caminar la distancia mínima para llegar a la salida. Esto es relativamente fácil de hacer con las luces encendidas, por supuesto, desde que ella caminará en sentido horario o sentido anti-horario desde su posición actual a la salida - por cualquiera dirección que sea la más corta.

Un día, se van las luces, causando que Bessie entre en pánico y se olvide en que punto está parada. Afortunadamente, ella aún recuerda el mapa del establo, por lo tanto ella puede darse cuenta de su posición actual caminando y usando su sentido del tacto. Cuando ella está en un vértice (incluyendo su vértice inicial), ella puede sentir exactamente el ángulo interior en ese vértice, y ella pueda decir si ese vértice es la salida. Cuando ella camino a lo largo de un lado del establo, ella puede determinar la longitud exacta del lado después de recorrer todo el lado. Bessie decide la siguiente estrategia: ella se moverá en sentido horario del perímetro del establo hasta que ella haya sentido suficientes ángulos y lados para deducir el vértice en el cual ella está ubicada actualmente. En ese punto, ella puede darse fácilmente cuenta de cómo llegar a la salida recorriendo una cantidad mínima de distancia restante, o continuar su movimiento en sentido horario o cambiando su dirección a sentido contra-horario. Por favor ayude a Bessie a determinar la cantidad mayor en la que se incrementará su distancia de recorrido en el peor caso (sobre todas las posibilidades para su vértice inicial) para desplazarse en la oscuridad versus en un establo iluminado.

Entrada

La primera línea de la entrada contiene ~N~ ~(4 \leq N \leq 200)~. Cada una de las siguientes ~N~ líneas contiene dos enteros, describiendo los puntos ~(x_i,y_i)~ en orden horario alrededor del establo. Esos enteros están en el rango ~-100,000...100,000~.

Salida

De como salida la cantidad más grande en que el recorrido de Bessie aumentará en el peor caso usando la estrategia dada en el enunciado del problema.

Ejemplo de Entrada

4
0 0
0 10
1 10
1 0

Ejemplo de Salida

2

En el ejemplo, Bessie puede sentir que ella está inicialmente parada en un ángulo de 90 grados, pero no puede decir si está parada inicialmente en vértice 2, 3 ó 4. Despues de recorrer un lado en la dirección horaria, Bessie puede llegar a la salida o puede determinar únicamente su posición basada en la longitud de este lado. Las distancias que ella obtiene son:

Si ella comienza en el vértice 2: ella recorre 12 unidades en la oscuridad (1 unidad para llegar al vértice 3, luego 11 unidades para continuar a la salida). Ella solamente necesita recorrer 10 unidades en el establo. Esta es una distancia extra de 2 unidades para este vértice) Si comienza en el vértice 3: ella recorre 11 unidades en ambos casos.

Si comienza en el vértice 4: ella viaja 1 unidad en ambos casos.

La peor diferencia sobre todos los puntos iniciales e por lo tanto ~12 - 10 = 2~. Eso es, Bessie puede garantizar que usando su estrategia, sin importar donde comience, ella se desplazará 2 unidades extra más de distancia en la oscuridad que en la luz.

USACO 2016 January Contest, Gold Problem 3. Lights Out.