Bessie は異常な流星群が来ると聞きました。報道によれば、流星は地上に衝突し、当たったものをすべて破壊します。安全が心配な彼女は、流星に永久に破壊されない安全な場所への道を探すと決めます。今は座標平面の原点で草を食べており、途中で流星に破壊されず、より安全な新しい場所へ移りたいのです。

$M$ 個の流星、$(1 \le M \le 50,000)$、が衝突します。流星 $i$ は時刻 $T_{i}$、$(0 \le T_{i} \le 1,000)$、に点 $(X_{i}, Y_{i})$、$(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$、を襲います。衝突点と上下左右に隣接する四つの格子点を破壊します。

Bessie は時刻 $0$ に原点を出発し、第一象限内で軸に平行に毎秒距離一単位を移動し、まだ破壊されていない隣接格子点（通常四つ）へ行けます。ある点が破壊される時刻以降は、その点にいられません。

安全な場所に到達する最短時間を求めてください。

入力

標準入力から読み取ります。

• 行 $1$：整数 $M$ 一つ。

• 行 $2,\ldots,M+1$：行 $i+1$ に空白区切りの三整数 $X_{i}$、$Y_{i}$、$T_{i}$。

出力

標準出力に書き出します。

• 行 $1$：到達する最短時間。不可能なら $-1$。

入出力例

入力 1

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

出力 1

5

注記

四つの流星がそれぞれ時刻 $2$、$2$、$2$、$5$ に $(0, 0)$、$(2, 1)$、$(1, 1)$、$(0, 3)$ を襲います。

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = 流星の衝突
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = 破壊された牧草地
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

上図の $t=5$ では最も近い安全な点は $(3, 0)$ ですが、第二の流星がそこへの道を早すぎる時点で塞ぎます。次に近い $(4,0)$ も早く塞がれます。その次は $(0,5)$-$(5,0)$ の対角線上の格子点です。そのうち $(0,5)$、$(1,4)$、$(2,3)$ はどれも $5$ 時間単位で到達できます。

       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    時刻ごとの Bessie の位置
       2|2 . . . . . .    一つの解の場合
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

問題作成者：Jeffrey Wang、2007