Farmer John instaló una sofisticada máquina de ordeño nueva en el establo, ¡pero consume tanto que a veces corta la electricidad! Ocurre tan a menudo que Bessie ha memorizado el plano para hallar la salida más fácilmente a oscuras. Sin embargo, le interesa cómo los cortes afectan su capacidad de salir rápidamente, por ejemplo cuánto más tendrá que caminar a oscuras.
El establo es un polígono simple (sin autointersecciones) con vértices enteros $(x_1, y_1) \ldots (x_n, y_n)$ en orden horario. Sus lados alternan entre horizontales (paralelos al eje $x$) y verticales (al eje $y$); el primero puede ser de cualquier tipo. La salida está en $(x_1, y_1)$. Bessie comienza en el establo en algún vértice $(x_i, y_i)$ con $i > 1$. Solo puede caminar por el perímetro en sentido horario o antihorario y quiere recorrer la distancia mínima a la salida. Con luz es fácil: elige el sentido más corto desde donde está.
Un día se apagan las luces y Bessie, presa del pánico, olvida en qué vértice está. Aún recuerda el plano exacto y puede averiguar su posición caminando y tocando. En cada vértice, incluido el inicial, siente el ángulo interior exacto y sabe si es la salida. Tras recorrer un lado completo, conoce su longitud exacta. Su estrategia es caminar en sentido horario hasta sentir suficientes ángulos y lados para deducir su vértice actual. Después toma el trayecto restante mínimo hacia la salida, continuando en sentido horario o cambiando al antihorario.
Determina el mayor incremento de distancia a oscuras frente al establo iluminado, en el peor caso entre todos los vértices iniciales.
Entrada
La primera línea contiene $N$ ($4 \leq N \leq 200$). Cada una de las siguientes $N$ líneas contiene dos enteros, los vértices $(x_i, y_i)$ en orden horario. Los enteros están en $-100,000 \ldots 100,000$.
Salida
Imprime el mayor incremento de distancia desde la peor posición inicial usando la estrategia descrita.
Ejemplos
Entrada 1
4 0 0 0 10 1 10 1 0
Salida 1
2
Nota
En el ejemplo, Bessie siente un ángulo inicial de 90 grados, pero no distingue los vértices 2, 3 y 4. Tras recorrer un lado en sentido horario, alcanza la salida o determina de forma única su posición según la longitud del lado. Las distancias son:
Desde el vértice 2: 12 unidades a oscuras (1 hasta el vértice 3 y luego 11 a la salida), y solo 10 con luz. La distancia extra es 2.
Desde el vértice 3: 11 unidades en ambos casos.
Desde el vértice 4: 1 unidad en ambos casos.
La peor diferencia es $12 - 10 = 2$. La estrategia garantiza, independientemente del inicio, como máximo 2 unidades adicionales a oscuras respecto a con luz.
Autor del problema: Brian Dean