题目描述

光头强听说一场非同寻常的流星雨即将来临；报道称，这些流星将撞击地球，摧毁它们撞击的任何物体。出于对自己安全的担忧，她发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。他目前正在坐标平面上的原点，想搬到一个新的、更安全的位置，同时避免被沿途的流星摧毁。

报道称，有 $M$ 个流星 $(1≤M≤50000)$ 将撞击，流星 $i$ 将在 $T_i(0≤T_i≤1000)$ 时撞击点 $(X_i,Y_i)(0≤X_i≤300;0≤Y_i≤300)$。每颗流星都会破坏它撞击的点，以及四个直线相邻的晶格点。

光头强在时间0离开原点，可以以每秒一个距离单位的速度在第一象限内平行于轴移动到尚未被流星摧毁的任何相邻点。光头强不能移动到已经被摧毁的点上，当然，也不能直接被击中（即到达某点的时间必须早于流行坠落的时间）。

确定光头强到达安全地点所需的最短时间。

输入格式

• 第 $1$ 行：单个整数：$M$。
• 第 $2..M+1$ 行：第 $i+1$ 行包含三个空格分隔的整数：$X_i,Y_i$ 和 $T_i$。

输出格式

• 第 $1$ 行：光头强到达安全地点所需的最短时间，如果不可能，则为 -1。

样例

4
0 0 2
2 1 2
1 1 2
0 3 5

5

提示

(0,0)→(0,1)→(0,2)→(0,3)→(0,4)→(1,4)