Bessie hört von einem außergewöhnlichen Meteorschauer: Die Meteore schlagen auf der Erde ein und zerstören alles, was sie treffen. Um ihre Sicherheit besorgt, sucht sie einen Weg zu einem sicheren Ort, der niemals durch einen Meteor zerstört wird. Sie weidet am Ursprung der Koordinatenebene und möchte unterwegs der Zerstörung entgehen und einen sichereren Ort erreichen.

$M$ Meteore schlagen ein, $(1 \le M \le 50,000)$. Meteor $i$ trifft $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, zum Zeitpunkt $T_{i}$, $(0 \le T_{i} \le 1,000)$. Er zerstört den Einschlagpunkt und die vier horizontal oder vertikal benachbarten Gitterpunkte.

Bessie verlässt den Ursprung zur Zeit $0$ und bewegt sich im ersten Quadranten achsenparallel mit einer Entfernungseinheit pro Sekunde zu einem noch nicht zerstörten Nachbarpunkt (oft vier). Ab dem Zeitpunkt seiner Zerstörung darf sie sich nicht an einem Punkt befinden.

Bestimme die minimale Zeit bis zu einem sicheren Ort.

Eingabe

Lies die Standardeingabe.

• Zeile $1$: eine ganze Zahl $M$.

• Zeilen $2,\ldots,M+1$: Zeile $i+1$ enthält drei durch Leerzeichen getrennte ganze Zahlen $X_{i}$, $Y_{i}$, $T_{i}$.

Ausgabe

Schreibe in die Standardausgabe.

• Zeile $1$: minimale Zeit oder $-1$, falls unmöglich.

Beispiele

Eingabe 1

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

Ausgabe 1

5

Hinweis

Vier Meteore treffen $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ zu den jeweiligen Zeiten $2$, $2$, $2$, $5$.

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = Meteoreinschlag
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = zerstörte Weide
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

Im Bild bei $t=5$ ist $(3, 0)$ der nächste sichere Punkt, doch der zweite Meteor versperrt seinen Weg zu früh. Auch der nächste, $(4,0)$, ist zu früh versperrt. Danach kommen Gitterpunkte auf der Diagonalen $(0,5)$-$(5,0)$. Davon sind $(0,5)$, $(1,4)$, $(2,3)$ in $5$ Zeiteinheiten erreichbar.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    Bessies Positionen im Zeitverlauf
       2|2 . . . . . .    für eine Lösung
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

Aufgabenautor: Jeffrey Wang, 2007