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