[Usaco2008 Feb]Meteor Shower流星雨

一场流星雨即将来袭。由于流星体积过大，它们无法在撞击地面前燃烧殆尽，会摧毁落点及其周围的区域。为了保证安全，芙蓉哥哥必须在被流星击中前到达一块永远不会受到流星影响的土地。

将地面看作直角坐标系，芙蓉哥哥初始位于原点 $(0,0)$ ，且只能在第一象限内移动。共有 $M$ 颗流星坠落，其中第 $i$ 颗流星会在时刻 $T_i$ 击中格子 $(X_i,Y_i)$ 。每颗流星会摧毁其落点以及上、下、左、右 $4$ 个相邻格子。被摧毁的格子从此不能进入。

芙蓉哥哥从时刻 $0$ 开始行动。每经过 $1$ 个单位时间，可以沿坐标轴方向移动到一个相邻格子，但到达该格子时，该格子必须尚未被摧毁。如果一个格子在时刻 $t$ 被流星直接击中或受到波及，那么芙蓉哥哥只能在严格早于 $t$ 的时刻位于该格子。

请计算芙蓉哥哥到达安全格子所需的最少时间。

输入格式

第一行包含一个正整数 $M$ ，表示流星的数量。

接下来 $M$ 行，第 $i$ 行包含三个用空格分隔的整数 $X_i$ 、 $Y_i$ 和 $T_i$ ，分别表示第 $i$ 颗流星的落点坐标和坠落时刻。

输出一个整数，表示芙蓉哥哥到达安全格子所需的最少时间。

如果无论如何都无法存活，输出 $-1$ 。

共有 $4$ 颗流星，它们的落点分别为 $(0,0)$ 、 $(2,1)$ 、 $(1,1)$ 和 $(0,3)$ ，坠落时刻分别为 $2$ 、 $2$ 、 $2$ 和 $5$ 。

本题为 USACO 2008 February 试题「Meteor Shower 流星雨」，题面与测试数据整理自 BZOJ。