小 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
定时炸弹坐标分别是 (0, 0)，(2, 1)，(1, 1) 以及 (0, 3)，爆炸时刻分别为 2，2，2，5 。
一个可行的行动方案是，沿着路径 (0,0)->(0,1)->(0,2)->(0,3)->(1,3)->(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。