Bessie apprend qu'une extraordinaire pluie de météores approche : ils heurteront la terre et détruiront tout ce qu'ils touchent. Inquiète pour sa sécurité, elle veut trouver un chemin vers un lieu sûr, jamais détruit par un météore. Elle broute actuellement à l'origine du plan et veut rejoindre un endroit plus sûr en évitant d'être détruite en chemin.

$M$ météores frapperont, $(1 \le M \le 50,000)$. Le météore $i$ frappe $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, à l'instant $T_{i}$, $(0 \le T_{i} \le 1,000)$. Il détruit ce point et les quatre points du réseau voisins horizontalement ou verticalement.

Bessie quitte l'origine à l'instant $0$, se déplace dans le premier quadrant parallèlement aux axes, à une unité de distance par seconde, vers un voisin non encore détruit (souvent quatre choix). Elle ne peut occuper un point à l'instant de sa destruction ni ensuite.

Déterminez le temps minimal pour atteindre un lieu sûr.

Entrée

Lisez sur l'entrée standard.

• Ligne $1$ : un entier $M$.

• Lignes $2,\ldots,M+1$ : la ligne $i+1$ contient trois entiers séparés par des espaces : $X_{i}$, $Y_{i}$, $T_{i}$.

Sortie

Écrivez sur la sortie standard.

• Ligne $1$ : temps minimal, ou $-1$ si impossible.

Exemples

Entrée 1

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

Sortie 1

5

Remarque

Quatre météores frappent $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ aux instants respectifs $2$, $2$, $2$, $5$.

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = impact de météore
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = pâturage détruit
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

Sur le dessin à $t=5$, le point sûr le plus proche est $(3, 0)$, mais le deuxième météore bloque trop tôt son chemin. Le suivant, $(4,0)$, est aussi bloqué trop tôt. Viennent ensuite les points de la diagonale $(0,5)$-$(5,0)$. Parmi eux, $(0,5)$, $(1,4)$, $(2,3)$ sont tous atteignables en $5$ unités de temps.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    positions de Bessie au fil du temps
       2|2 . . . . . .    pour une solution
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

Auteur du problème : Jeffrey Wang, 2007