题目描述

七天后，有一场特别的流星雨即将到来，这些流星会撞向地球，并摧毁它们所撞击的任何东西。

小田现在为自己的安全感到焦虑，他发誓要找一个安全的地方（指永远不会被流星摧毁的地方）躲起来。

如果将小田所在的地方放入一个直角坐标系里面，那么小田现在的位置是原点 $(0,0)$。

根据预报，一共有 $M$ 颗流星会坠落，其中第 $i$ 颗流星会在时刻 $T_i$ 砸在坐标为 $(X_i, Y_i)$ 的格子里，流星的力量会将它所在的格子以及上下左右 $4$ 个相邻的格子都化为焦土，小田无法移动到化为焦土的格子。

现在，小田在时刻 $0$ 开始行动，他只能在坐标 $X,Y \ge 0$ 的区域中移动，你可以把这片区域视为无穷大。

每 $1$ 时刻他能移动到上下左右四个格子中的任意一个，需要注意的是，如果一个格子在时刻 $t$ 被流星撞击或烧焦，那么小田只能在 $t$ 时刻之前能走这个格子。

小田初始在 $(0, 0)$ 的位置，请你计算一下，小田最少需要多少时间才能到达一个安全的格子，如果小田注定无法逃脱被流星砸的命运，请输出 $-1$。

输入格式

第一行输入一个整数 $m$，表示流星的数量。

接下来 $m$ 行，每行输入三个整数 $x,y,t$，表示流星坠落的位置和时间。

输出格式

输出一个数字，表示小田到达安全地点所需的最短时间；如果不可能，输出 $-1$。

样例 #1

样例输入 #1

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

样例输出 #1

5

提示

【数据范围】

$1 \le M \le 50000, 0 \le t \le 1000, 0 \le x,y \le 300$