#714. [USACO08FEB]Meteor Shower S

[USACO08FEB]Meteor Shower S

题目描述

贝茜听说了一个骇人听闻的消息:一场流星雨即将袭击整个农场,由于流星体积过大,它们无法在撞击到地面前燃烧殆尽,届时将会对它撞到的一切东西造成毁灭性的打击。很自然地,贝茜开始担心自己的安全问题。以 Farmer John 牧场中最聪明的奶牛的名誉起誓,她一定要在被流星砸到前,到达一个安全的地方(也就是说,一块不会被任何流星砸到的土地)。如果将牧场放入一个直角坐标系中,贝茜现在的位置是原点,并且,贝茜不能踏上一块被流星砸过的土地。 根据预报:

一共有 M 颗流星 (1M50,000)(1≤M≤50,000) 会坠落在农场上,其中第i颗流星会在时刻 Ti(0Ti1,000)T_i(0≤T_i≤1,000) 砸在坐标为 (Xi,Yi)(0Xi300,0Yi300)(X_i, Y_i) (0\leq X_i\leq 300,0\leq Y_i\leq300)的格子里。流星的力量会将它所在的格子,以及周围 4 个相邻的格子都化为焦土,当然贝茜也无法再在这些格子上行走。

贝茜在时刻 0 开始行动,它只能在第一象限中,平行于坐标轴行动,每 1 个时刻中,她能移动到相邻的(一般是 4 个)格子中的任意一个,当然目标格子要没有被烧焦才行。如果一个格子在时刻 t 被流星撞击或烧焦,那么贝茜只能在 t 之前的时刻在这个格子里出现。 贝西一开始在(0,0)(0,0)

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

输入格式

输入共22

第一行:一个整数 MM

22行……到第M+1M+1行:每行三个整数XiXi YiYi TiTi

输出格式

贝西到达安全地点所需的最短时间,如果不可能,则为-1。

样例

输入样例1

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

输出样例1

5