题目描述

小灰听说一场罕见的冰雹即将来袭：冰雹会砸向草原，并毁掉被砸中的一切。它十分担心自己的安危，决心找到一处永远不会被冰雹砸毁的地方躲起来。

把草原放进平面直角坐标系中，小灰当前位于原点，并且它绝不能踏上一块被冰雹砸过的土地。

根据预报，一共有 $M$ 颗冰雹 $(1\leq M\leq 50,000)$ 会落在草原上，其中第 $i$ 颗冰雹会在时刻 $T_i$（$0 \leq T_i \leq 1000$）砸中坐标为 $(X_i,Y_i)$（$0\leq X_i\leq 300$，$0\leq Y_i\leq 300$）的格子。冰雹的冲击会把它所在的格子以及四周 $4$ 个相邻格子都化为焦土，小灰之后也无法再在这些格子上行走。

小灰在时刻 $0$ 出发，它只能在横、纵坐标 $X,Y\ge 0$ 的区域内，沿平行于坐标轴的方向移动；每 $1$ 个时刻，它可以移动到相邻（一般是 $4$ 个）格子中的任意一个，当然目标格子不能已被砸毁。如果一个格子在时刻 $t$ 被冰雹砸中或波及，那么小灰只能在 $t$ 之前的时刻出现在这个格子里。小灰一开始位于 $(0,0)$。

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

输入格式

共 $M+1$ 行。第 $1$ 行输入一个整数 $M$；接下来的 $M$ 行，每行输入三个整数，依次为 $X_i, Y_i, T_i$。

输出格式

输出一行一个整数：小灰到达安全地点所需的最短时间；如果不可能，输出 $-1$。

样例

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

5