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$ 離開原點，只能在第一象限內沿平行於座標軸的方向移動，每秒移動一個距離單位，到尚未被流星摧毀的相鄰格點（通常有四個）。牠不能在一個點被摧毀的時刻或之後位於該點。

求 Bessie 到達安全地點的最短時間。

輸入格式

從標準輸入讀取資料。

• 第 $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)$，但第二顆流星過早阻斷了 Bessie 通往它的路徑。下一個最近點 $(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