题目描述

小明从时刻 $0$ 开始站在坐标 $(0,0)$。每经过一个单位时间，他必须向上、下、左、右四个方向之一移动一格，并且始终只能到达横纵坐标均为非负整数的位置。

战场上有 $m$ 枚炸弹。第 $i$ 枚炸弹在时刻 $t_i$ 爆炸，会永久破坏 $(x_i,y_i)$ 以及与它上下左右相邻的四个位置。如果某个位置在时刻 $t$ 被破坏，小明只能在时刻 $t$ 之前到达该位置。

一个永远不会被任何炸弹破坏的位置称为安全位置。请计算小明到达安全位置的最短时间；如果无法到达，输出 $-1$。同一位置可能有多枚炸弹。

输入格式

第一行包含一个整数 $m$，表示炸弹数量。

接下来 $m$ 行，每行包含三个整数 $x_i,y_i,t_i$。

输出格式

输出一个整数，表示到达安全位置的最短时间；如果无法到达，输出 $-1$。

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

5

数据范围与提示

• $1 \le m \le 50000$
• $0 \le x_i,y_i \le 300$
• $0 \le t_i \le 1000$