Bessie oye que se acerca una lluvia extraordinaria de meteoros; los reportes dicen que estos meteoros chocarán con la tierra y destruirán cualquier cosa que toquen. Ansiosa por su seguridad, ella clama encontrar su camino a una ubicación segura (una que nunca sea destruida por un meteoro). Ella está actualmente pasteando en el origen del plano de coordenadas y quiere moverse a una ubicación nueva, segura asegurándose de no ser destruida por meteoros en el camino. Los reportes dicen que ~M~ meteoros ~(1 \leq M \leq 50 000)~ caerán, el meteoro ~i~ caerá en el punto ~(X_i, Y_i) (0 \leq X_i \leq 305; 0 \leq Y_i \leq 305)~ en el tiempo ~T_i (0 \leq T_i \leq 1 000)~. Cada meteoro destruye el punto en el cual cae y también los cuatro puntos adyacentes de coordenadas enteras. Bessie parte del origen en el tiempo 0 y puede viajar en el primer cuadrante y paralela a los ejes con un velocidad de una unidad de distancia por segundo a cualquier de los (frecuentemente 4) puntos adyacentes rectilíneamente que aún no están destruidos por un meteoro. Ella no puede ser ubicada en un punto en cualquier tiempo mayor o igual al tiempo en el cual él es destruido. Determine el tiempo mínimo que le toma a Bessie llegar a una ubicación segura.

Entrada

• Línea 1: Un solo entero: ~M~.

• Líneas 2…M+1: La línea ~i+1~ contiene tres enteros separados por espacios: ~X_i, Y_i,~ y ~T_i~.

Ejemplo de Entrada

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

Detalles de la Entrada

Hay cuatro meteoros, que caerán en los puntos ~(0, 0); (2, 1); (1, 1);~ y ~(0, 3)~ en los tiempos ~2, 2, 2,~ y ~5,~ respectivamente.

    t = 0              t = 2            t = 5
5|. . . . . . .   5|. . . . . . .   5|. . . . . . .    
4|. . . . . . .   4|. . . . . . .   4|# . . . . . .   * = impacto 
3|. . . . . . .   3|. . . . . . .   3|* # . . . . .       del meteoro
2|. . . . . . .   2|. # # . . . .   2|# # # . . . .   # = pasto 
1|. . . . . . .   1|# * * # . . .   1|# # # # . . .       destruido
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

Salida

• Línea 1: El tiempo mínimo que le toma a Bessie llegar a una ubicación segura ó -1 si es imposible.

Ejemplo de Salida

5

Detalles de la Salida

Examinando el dibujo antes mostrado en ~t~ = 5, el punto seguro más cercano es ~(3, 0)~ – pero el camino de Bessie a ese punto está bloqueado muy rápidamente por el segundo meteoro. El siguiente punto más cercano es ~(4,0)~ – también bloqueado muy rápido. Los puntos de intersección más cercanos después de ellos son lo que están en la diagonal ~(0,5)-(5,0)~. De estos, cualquiera de ~(0,5), (1,4),~ y ~(2,3)~ es alcanzable en 5 unidades de tiempo.

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