Bessie słyszy o nadchodzącym niezwykłym deszczu meteorów: uderzą w ziemię i zniszczą wszystko, co trafią. Zaniepokojona bezpieczeństwem postanawia znaleźć drogę do bezpiecznego miejsca, nigdy niezniszczonego przez meteor. Pasie się w początku układu współrzędnych i chce przejść w bezpieczniejsze miejsce, unikając zniszczenia po drodze.

Spadnie $M$ meteorów, $(1 \le M \le 50,000)$. Meteor $i$ trafi $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$, w chwili $T_{i}$, $(0 \le T_{i} \le 1,000)$. Niszczy punkt trafienia i cztery sąsiednie punkty kratowe w poziomie lub pionie.

Bessie opuszcza początek w chwili $0$ i porusza się w pierwszej ćwiartce równolegle do osi z prędkością jednostki odległości na sekundę do dowolnego jeszcze niezniszczonego sąsiada (często czterech). Nie może być w punkcie w chwili jego zniszczenia ani później.

Wyznacz minimalny czas dojścia do bezpiecznego miejsca.

Wejście

Czytaj ze standardowego wejścia.

• Wiersz $1$: jedna liczba całkowita $M$.

• Wiersze $2,\ldots,M+1$: wiersz $i+1$ zawiera trzy całkowite rozdzielone spacjami: $X_{i}$, $Y_{i}$, $T_{i}$.

Wyjście

Pisz na standardowe wyjście.

• Wiersz $1$: minimalny czas lub $-1$, gdy niemożliwe.

Przykład

Wejście 1

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

Wyjście 1

5

Uwagi

Cztery meteory trafiają $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$ odpowiednio w chwilach $2$, $2$, $2$, $5$.

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = uderzenie meteoru
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = zniszczone pastwisko
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

Na rysunku przy $t=5$ najbliższy bezpieczny punkt to $(3, 0)$, lecz drugi meteor zbyt wcześnie blokuje drogę. Następny, $(4,0)$, też jest blokowany zbyt wcześnie. Dalej są punkty przekątnej $(0,5)$-$(5,0)$. Spośród nich $(0,5)$, $(1,4)$, $(2,3)$ można osiągnąć w $5$ jednostkach czasu.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    pozycje Bessie w czasie
       2|2 . . . . . .    dla jednego rozwiązania
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

Autor zadania: Jeffrey Wang, 2007