Bessie ouve que vem uma extraordinária chuva de meteoros: eles atingirão a terra e destruirão tudo em que baterem. Preocupada, decide achar um caminho para um lugar seguro, nunca destruído por meteoro. Pasta na origem do plano e quer ir a um local mais seguro evitando ser destruída no caminho.

Cairão $M$ meteoros, $(1 \le M \le 50,000)$. O $i$ atinge $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, no instante $T_{i}$, $(0 \le T_{i} \le 1,000)$. Destrói esse ponto e os quatro pontos da malha vizinhos horizontal ou verticalmente.

Bessie sai da origem no instante $0$ e anda no primeiro quadrante paralelamente aos eixos, uma unidade de distância por segundo, para qualquer vizinho ainda não destruído (geralmente quatro). Não pode estar num ponto no instante da destruição nem depois.

Determine o tempo mínimo para chegar a um lugar seguro.

Entrada

Leia da entrada padrão.

• Linha $1$: um inteiro $M$.

• Linhas $2,\ldots,M+1$: a linha $i+1$ contém três inteiros separados por espaços: $X_{i}$, $Y_{i}$, $T_{i}$.

Saída

Escreva na saída padrão.

• Linha $1$: tempo mínimo ou $-1$ se impossível.

Exemplos

Entrada 1

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

Saída 1

5

Observação

Quatro meteoros atingem $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ nos instantes 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|# # # . . . .   # = pastagem destruída
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

No desenho em $t=5$, o ponto seguro mais próximo é $(3, 0)$, mas o segundo meteoro bloqueia cedo demais o caminho. O seguinte, $(4,0)$, também é bloqueado cedo demais. Seguem os pontos da diagonal $(0,5)$-$(5,0)$. Desses, $(0,5)$, $(1,4)$, $(2,3)$ são alcançáveis em $5$ unidades de tempo.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    posições de Bessie ao longo do tempo
       2|2 . . . . . .    para uma solução
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

Autor do problema: Jeffrey Wang, 2007