贝茜听到一场非同寻常的流星雨( meteor shower)即将来临;有报道称这些流星将撞击地球并摧毁它们所击中的任何东西。为了安全起见(Anxious for her safety), ，她发誓（vows）要找到一条路到安全的地方(一个从未被流星摧毁的地方)。目前，她在坐标轴（coordinate plane）的原点上，想要移动到一个新的，更安全的位置，同时在路上避免流星砸到。
报道说，在时间Ti（0≤Ti≤1000）的情况下，M(1 ≤ M ≤ 50,000) 颗流行将会坠落（strike）,流星i会摧毁点 (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300)。每颗流星都破坏了它撞击的点，也破坏了该点的四个相邻的格子点
贝西在时间0的时候离开原点，可以在第一象限移动，并以每秒一个距离单位的速度移动到任何一个(通常是4)相邻的方格点，而不是被流星摧毁。她不能在任何时候都处于大于或等于它被毁灭的时间。
确定贝西到达一个安全地点的最小时间。
Input
* Line 1: A single integer: M
* Lines 2..M+1: Line i+1 contains three space-separated integers: Xi, Yi, and Ti
Output
* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.
Sample Input
4 0 0 2 2 1 2 1 1 2 0 3 5
Sample Output
5