该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

D. 定时炸弹

题目描述

小 A 误入一个危险的星际战场，战场上暗藏了 $m$ 枚定时炸弹。他需要前往一个安全的地方躲起来。 如果把战场作为一个直角坐标系，小 A 目前所在的位置为坐标轴的原点。小 A 要找的安全位置，是一个一定不会被炸弹炸到的位置。

已知第 $i$ 枚定时炸弹会在第 $t_i$ 时刻于 $(x_i,y_i)$ 位置爆炸，爆炸会对其所在位置，以及上下左右四方向相邻的格子造成破坏，胆小的小 A 当然不会躲在被破坏过的位置上，也不会途经这些位置。

小 A 位于 \((0,0)\) 从 0 时刻开始移动，每单位时间只能向相邻的四个方向任意一个移动，且任意时刻他都只能位于坐标值为非负整数的位置上。如果一个格子在时刻 $t$ 被炸弹破坏，那么小 A 只能在 $t$ 之前的时刻在这个格子里出现。

那么小 A 到达安全位置最少需要多少单位时间。如果不可能到达则输出 $-1$。

输入

第 1 行输入一个正整数 $m$。 接下来的 $m$ 行每行输入三个整数分别为 $x_i,y_i,t_i$，变量含义如题所述。

测试数据确保如果位置 \((0,0)\) 处有炸弹，该炸弹一定不会在 0 时刻爆炸。但请注意，同一个位置可能有多个炸弹。

输出

输出小 A 到达安全位置需要的最少单位时间，如果不可能，则为 $-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

输出

3

输入

23
2 5 10
1 3 5
5 3 12
3 3 9
1 8 7
8 4 15
2 3 7
0 0 2
6 7 10
4 4 10
3 7 7
8 5 13
0 4 9
2 6 8
0 2 4
6 4 12
0 6 7
4 2 10
1 4 7
4 6 10
5 5 12
6 5 14
2 1 2

输出

13

说明

【样例1解释】 定时炸弹坐标分别是 $(0,0),(2,1),(1,1)$ 以及 $(0,3)$，爆炸时刻分别为 \(2,2,2,5\)。 一个可行的行动方案是，沿着路径 $((0,0)\to(0,1)\to(0,2)\to(0,3)\to(1,3)\to(2,3)$ 最快需要 5 个单位时间到达 $(2,3)$ 点即可安全。

数据范围

• 对于 10% 的测试数据，满足 $m=2$。
• 对于 50% 的测试数据，满足 $1 \le m \le 300$。
• 对于 100% 的测试数据，满足 $1 \le m \le 50000,\ 0 \le x_i,y_i \le 300,\ 0 \le t_i \le 1000$。