贝茜听说了一个骇人听闻的消息：一场流星雨即将袭击整个农场，由于流星体积过大，它们无法在撞击到地面前燃烧殆尽，届时将会对它撞到的一切东西造成毁灭性的打击。很自然地， 贝茜开始担心自己的安全问题。以 FJ 牧场中最聪明的奶牛的名誉起誓，她一定要在被流星砸到前，到达一个安全的地方（也就是说，一块不会被任何流星砸到的土地）。

如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土 地。

根据预报，一共有 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)$的格子里。流星的力量会将它所在的格子，以及周围 4 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。

贝茜在时刻 0 开始行动，它只能在第一象限中，平行于坐标轴行动，每 1 个时刻中，她能 移动到相邻的（一般是 4 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦，那么贝茜只能在 t 之前的时刻在这个格子里出现。

请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。

输入格式

第 1 行: 1 个正整数：M

第 2..M+1 行: 第 i+1 行为 3 个用空格隔开的整数：$X_i，Y_i，以及 T_i$

输出格式

第 1 行: 输出 1 个整数，即贝茜逃生所花的最少时间

如果贝茜无论如何都无法在流星雨中 存活下来，输出-1

样例

样例输入

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

【输入说明】一共有 4 颗流星将坠落在农场，它们落地点的坐标分别是(0, 0)，(2, 1)，(1, 1)以及(0, 3)，时刻分别为 2，2，2，5。  
      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  

样例输出

5

【输出说明】如果我们观察在 t=5 时的牧场，可以发现离贝茜最近的安全的格子是(3,0)—— 不过由于早在第二颗流星落地时，贝茜
直接跑去(3,0)的路线就被封死了。离贝茜第二近的安全格子为(4,0)，但它的情况也跟(3,0)一样。再接下来的格子就是在(0,5)-(5,0)
这条直 线上。在这些格子中，(0,5)，(1,4)以及(2,3)都能在 5 个单位时间内到达。
5|. . . . . . .      
4|. . . . . . .        
3|3 4 5 . . . . 某个合法的逃生方案中     
2|2 . . . . . . 贝茜每个时刻所在地点     
1|1 . . . . . .        
0|0 . . . . . .        
 --------------      
  0 1 2 3 4 5 6  

来源

图论练习

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$131072\mathrm{KB}$