Bessie oye que viene una extraordinaria lluvia de meteoros: chocarán contra la tierra y destruirán todo lo que golpeen. Preocupada, decide hallar un camino a un lugar seguro, nunca destruido por un meteoro. Pasta en el origen del plano y quiere trasladarse a un lugar más seguro evitando ser destruida por el camino.

Caerán $M$ meteoros, $(1 \le M \le 50,000)$. El $i$ golpea $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, en $T_{i}$, $(0 \le T_{i} \le 1,000)$. Destruye ese punto y los cuatro puntos de la retícula adyacentes horizontal o verticalmente.

Bessie sale del origen en tiempo $0$ y viaja en el primer cuadrante paralelamente a los ejes, una unidad de distancia por segundo, hacia cualquier vecino no destruido aún (a menudo cuatro). No puede estar en un punto en el momento de su destrucción ni después.

Determina el tiempo mínimo hasta un lugar seguro.

Entrada

Lee de la entrada estándar.

• Línea $1$: un entero $M$.

• Líneas $2,\ldots,M+1$: la línea $i+1$ contiene tres enteros separados por espacios: $X_{i}$, $Y_{i}$, $T_{i}$.

Salida

Escribe en la salida estándar.

• Línea $1$: tiempo mínimo o $-1$ si es imposible.

Ejemplos

Entrada 1

4
0 0 2
2 1 2
1 1 2
0 3 5

Salida 1

5

Nota

Cuatro meteoros golpean $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ en los tiempos respectivos $2$, $2$, $2$, $5$.

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = impacto de meteoro
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = pastizal destruido
1|. . . . . . .     1|# * * # . . .     1|# # # # . . .   
0|B . . . . . .     0|* # # . . . .     0|# # # . . . .   
  --------------      --------------      -------------- 
  0 1 2 3 4 5 6       0 1 2 3 4 5 6       0 1 2 3 4 5 6

En el dibujo para $t=5$, el punto seguro más cercano es $(3, 0)$, pero el segundo meteoro bloquea demasiado pronto su camino. El siguiente, $(4,0)$, también queda bloqueado demasiado pronto. Siguen los puntos de la diagonal $(0,5)$-$(5,0)$. De ellos, $(0,5)$, $(1,4)$, $(2,3)$ son alcanzables en $5$ unidades de tiempo.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    posiciones de Bessie con el tiempo
       2|2 . . . . . .    para una solución
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

Autor del problema: Jeffrey Wang, 2007