#708. 小码君的胜利逃亡

小码君的胜利逃亡

题目描述

小码君终于如愿以偿的找到了藏宝图上的宝物,不过因为取走了宝物,被宝物镇压的恐怖妖魔马上就要复苏了,妖魔将要释放法术开始无差别的攻击范围内的所有地方。

小码君需要在妖魔彻底复苏前到达一个安全的地方(也就是说,一块不会被任何法术轰炸的地方)。

如果将地图放入一个直角坐标系中,小码君现在的位置是原点,并且,小码君不能踏上一块被法术轰炸的土地。

根据宝物给出的预知,一共有 MM 个法术 (1M50,000)(1\leq M\leq50,000) 会轰炸在地面上,其中第i个法术会在时刻 TiT_i (0Ti1,000)(0\leq T_i\leq1,000) 砸在坐标为 (Xi,Yi)(X_i, Y_i) (0Xi300(0\leq X_i\leq 3000Yi300)0\leq Y_i\leq300) 的格子里。法术的力量会将它所在的格子,以及周围 44 个相邻的格子都化为焦土,当然小码君也无法再在这些格子上行走。

小码君在时刻 00 开始行动,它只能在第一象限中,平行于坐标轴行动,每 11 个时刻中,他能移动到相邻的(一般是 44 个)格子中的任意一个,当然目标格子要没有被烧焦才行。如果一个格子在时刻 tt 被法术轰炸或烧焦,那么小码君只能在 tt 之前的时刻在这个格子里出现。 小码君一开始在(0,0)(0,0)

请你计算一下,小码君最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 1-1

输入格式

第一行,一个整数M

第2至M+1行,每行三个整数,分别为当前法术的 Xi,Yi,TiX_i, Y_i, T_i

输出格式

输出小码君到达一个安全位置的时间,如果没有安全位置输出-1

样例 #1

样例输入 #1

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

样例输出 #1

5