题目描述

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

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

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

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

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

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

输入格式

一个正整数M

接下来M行，每行3个整数Xi，Yi和Ti。分别表示第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<=25

40% M<=200

100% M<=50000 0 <= X_i <= 300；0 <= Y_i <= 300 0 <= T_i <= 1,000

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$