题目描述
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
样例输入
样例输出