题目描述

流星雨是美丽的，但是流星落下来也能砸死人的。

有一大片流星要在草原落下，而小qt恰好在草原数星星。小qt面临最大的问题不是浪漫，而是保住小命。

我们把草原认为是坐标系的第一象限(以样例解释的图例为准)。小qt现在位于坐标系的原点。

现在有M颗流星会落在草原上，其中第i颗流星会在时刻 $T_i$ 砸在坐标为$(X_i, Y_i)$的格子里。流星的力量会将它所在的格子，以及周围4个相邻的格子都化为焦土，当然小qt也无法再在这些格子上行走，这样他会被烧伤。

小qt从0时刻开始逃离，他只能上下左右移动，并且一个时刻只能移动一个格子，当然，这个格子必须是完好的。

现在小qt想知道，最少经过多少时刻，他可以到达一个安全的格子。

输入格式

一个正整数M 接下来M行，每行3个整数 $X_i，Y_i和T_i$。分别表示第 $i$ 颗流星落下的坐标和时间。保证所有坐标都在第一象限。

输出格式

一个整数，表示最少逃离时刻。如果逃离不了，那么输出-1，表示小qt肯定被流星砸着了。

样例

input

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

output

5

【样例说明】

一共有4颗流星将坠落在操场，它们落地点的坐标分别是(0, 0)，(2, 1)，(1, 1)以及(0, 3)，时刻分别为2，2，2，5。

在t=5时的牧场，离小qt最近的安全的格子是(3,0)——不过由于早在第二颗流星落地时，小qt直接跑去(3,0)的路线就被封死了。离小qt第二近的安全格子为(4,0)，但它的情况也跟(3,0)一样。再接下来的格子就是在(0,5)-(5,0)这条直线上。在这些格子中，(0,5)，(1,4)以及(2,3)都能在5个单位时间内到达。

限制与提示

对于 $20\%$ 的数据， $M\leq25$。

对于 $40\%$ 的数据， $M\leq200$。

对于 $100\%$ 的数据， $100\% M \leq 50000; 0 \leq X_i \leq 300；0 \leq Y_i \leq 300; 0 \leq T_i \leq 1,000$。