几乎毁灭牛市的流星雨
题号：NC207759
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

考古队员发现，牛市之所以会有那么多古老遗迹，是因为牛市曾经遭遇过一场几乎毁灭了他的流星雨，那场流星雨中流星体积很大，无法在撞击到地面前燃烧完，所以对牛市几乎造成了毁灭性的打击，但是，我们牛市的先民也是很厉害的，他们对于流星雨的预报虽然没有提前太多的时间但是详细到了每颗流星坠落的位置，所以虽然牛市在那一场流星雨之后满目疮痍，但是牛市的百姓大多都存活了下来。因为自然环境受到了巨大的破坏，他们记录下了这段历史搬到其他的地方繁衍生息，很多代人之后，牛市的自然环境有了恢复，他们后代中的一些人又搬了回来，逐渐建成了现在的牛市。这段历史被遗忘被尘封多年，但终于还是没有被遗忘……
根据遗迹中某个记载，当时先民们预报了一共有M颗流星会坠落，他们将牛市划分成网格，他们预报其中第i颗流星会在时刻砸在坐标为的格子里。流星的力量会将它所在的格子，以及周围4个相邻的格子都化为焦土，在整个流星雨结束之前，这些格子都将无法行走站立。
现在有一个家族，在0时刻在0行0列的格子里，因为道路和建筑的原因，他们只能平行于坐标轴行动，每1个时刻，他们能移动到相邻的4个格子中的任意一个，当然这个格子要没有被撞击烧焦才行。（也就是说如果一个格子在时刻t被流星撞击或烧焦，那么他们只能在t之前的时刻在这个格子里出现。）
请你计算，这个家族是否在这场流星雨中幸存（移动到了一个没有被撞击或者烧焦的格子里一直待到流星雨结束），如果幸存，他们最少要花多少时间才移动到安全的格子里。
注：虽然流星只是砸在x，y坐标300的范围内，但是我们可以认为牛市在整个第一象限之内，即移动过程中x和y都可以超出300（但不能为负）。



输入描述:

第1行: 1个正整数：M
第2..M+1行: 第i+1行为3个用空格隔开的整数：X_i, Y_i,T_i

输出描述:

输出1个整数，即这个家族逃生所花的最少时间。如果这个家族无论如何都无法在流星雨中存活下来，输出-1
示例1

输入

复制 
4
0 0 2
2 1 2
1 1 2
0 3 5

输出

复制 
5

说明

这个家族最后待在了(0,5)，(1,4)或者(2,3)这三个格子其中之一，他们都可以在5单位时间到达