当前没有测试数据。

题目描述

小 $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

数据范围

对于 $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$。