【问题描述】

你说的对，但故事是我瞎编的。游戏发生在一个被称作「第一象限」的直角坐标系中，在这里，$x < 0$ 或 $y < 0$ 的范围是被称为不可抵达的暗之外海。小小莹将扮演一位名为「旅行者」的神秘角色，于沉睡中苏醒，并结识小小派相伴而行，为了找回失散的亲人，小小莹需要在自由的旅行中邂逅故事。

然而，随着「禁忌知识」的溢出，越来越多的地方出现「深渊污染」，小小莹的向导小小派预知到，这片大陆即将发生 $M$ 次污染，其中第 $i$ 次污染会在时刻 $Ti$ 出现在坐标 $(X_i, Y_i)$ 出，这将导致污染所在的格子，以及周围4个相邻的格子都化为「死地」，小小莹将无法踏足任何「死地」。

小小莹于零点 $(T = 0)$ 时刻在原点 $(0,0)$ 苏醒，并且只能在 $x\ge 0$ 且 $y\ge 0$ 的范围、平行于坐标轴行动；在每一个时刻，小小莹可以移动到相邻（一般是4个）格子中的任意一个，前提是格子还没有被污染为「死地」。如果一个格子在时刻 $t$ 被污染，那小小莹只能在时刻 $t$ 之前出现在这个格子中。

小小莹的血亲在遥远的 $S(x_s,y_s)$ 处，保证 $S$ 点远离污染处，即 $x_s>>X_i$ 或 $y_s>>Y_i$ ，她需要先躲避这场灾难、然后邂逅足够多的故事，并且最终一定能与血亲相见，她想知道，最快什么时候可以抵达安全点。

安全点定义为：不会遭受到「污染」，并且无论何时最终都可以移动到血亲处的位置。

【格式】

【输入】

共 $M+1$ 行

第一行一个整数 $M$ 。

接下来的 $M$ 行每行输入三个正整数，分别为 $X_i, Y_i, T_i$ 。

【输出】

小小莹抵达安全点所需要的最短时间，如果不可能，则为 -1 。

【样例】

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

5

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

-1

【数据说明】