Bessie听说有一场壮丽的流星雨即将来临，而且据说陨石将要落下来撞击地球并摧毁一切它遇到的东西。为了保证自己的安全，bessie决定到一个安全的（永远不会被陨石击毁）地方去。

报道表明将有M颗陨石落下（1 ≤ M ≤ 50,000)，第i个陨石将在Ti(0 ≤ Ti ≤ 1,000)时刻砸中（Xi,Yi)点(0 ≤ Xi ≤ 300； 0 ≤ Yi ≤ 300) 。每颗陨石将击毁它直接砸中的点以及四个与其直接相邻的点

她现在所处的地方是坐标系的原点，并从零时刻起出发，前往一个安全的地点，要求是她经过某点时该点未被击毁。她只能在坐标系的第一象限以及x，y轴的正半轴上活动。

求她能到达一个安全地点的最短时间。

第一行：陨石个数M

第二行至第M+1行：第i+1行有三个整数表示：Xi,Yi,和Ti

数据范围见题目描述

输出只有一行，即bessie所需的最短时间。如果她永远无法到达一个安全的地方，输出-1