Meteor Shower

Bessie hears that an extraordinary meteor shower is coming: reports say the meteors will crash into the ground and destroy anything they hit. Worried for her safety, she resolves to reach a safe location — a lattice point that is never destroyed by any meteor.

She starts grazing at the origin $(0, 0)$ of the coordinate plane and wants to move to a safer spot while avoiding the meteors along the way.

The reports say that $M$ meteors will strike. Meteor $i$ hits the point $(X_i, Y_i)$ at time $T_i$. Each meteor destroys the point it strikes together with the four rectilinearly adjacent lattice points (up, down, left, and right).

Bessie leaves the origin at time $0$. She stays in the first quadrant (all coordinates $\ge 0$) and moves parallel to the axes at a rate of one unit of distance per second, stepping to any adjacent lattice point that has not yet been destroyed. She can never occupy a point at a time greater than or equal to the moment that point is destroyed.

Determine the minimum time Bessie needs to reach a safe point, or report that it is impossible.

Constraints: $1 \le M \le 50000$, $0 \le X_i \le 300$, $0 \le Y_i \le 300$, $0 \le T_i \le 1000$.

• Line 1: a single integer $M$.
• Lines 2 to $M+1$: line $i+1$ contains three space-separated integers $X_i$, $Y_i$, and $T_i$.

• Line 1: the minimum time it takes Bessie to reach a safe point, or $-1$ if it is impossible.

In the sample there are four meteors, striking points $(0, 0)$, $(2, 1)$, $(1, 1)$, and $(0, 3)$ at times $2$, $2$, $2$, and $5$ respectively.

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = meteor impact
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = destroyed pasture
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 

At $t = 5$ the closest safe point is $(3, 0)$, but Bessie's path there is blocked too quickly by the second meteor. The next closest, $(4, 0)$, is also blocked too soon. After that come the lattice points on the diagonal from $(0, 5)$ to $(5, 0)$; of those, any one of $(0, 5)$, $(1, 4)$, and $(2, 3)$ can be reached in $5$ time units.

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    Bessie's positions over time
       2|2 . . . . . .    for one solution
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6