题目描述

小码君终于如愿以偿的找到了藏宝图上的宝物，不过因为取走了宝物，被宝物镇压的恐怖妖魔马上就要复苏了，妖魔将要释放法术开始无差别的攻击范围内的所有地方。

小码君需要在妖魔彻底复苏前到达一个安全的地方（也就是说，一块不会被任何法术轰炸的地方）。

如果将地图放入一个直角坐标系中，小码君现在的位置是原点，并且，小码君不能踏上一块被法术轰炸的土地。

根据宝物给出的预知，一共有 $M$ 个法术 $(1\leq M\leq50,000)$ 会轰炸在地面上，其中第i个法术会在时刻 $T_i$ $(0\leq T_i\leq1,000)$ 砸在坐标为 $(X_i, Y_i)$ $(0\leq X_i\leq 300$，$0\leq Y_i\leq300)$ 的格子里。法术的力量会将它所在的格子，以及周围 $4$ 个相邻的格子都化为焦土，当然小码君也无法再在这些格子上行走。

小码君在时刻 $0$ 开始行动，它只能在第一象限中，平行于坐标轴行动，每 $1$ 个时刻中，他能移动到相邻的（一般是 $4$ 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 $t$ 被法术轰炸或烧焦，那么小码君只能在 $t$ 之前的时刻在这个格子里出现。 小码君一开始在$(0,0)$。

请你计算一下，小码君最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 $-1$。

输入格式

第一行，一个整数M

第2至M+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