Sample Input 

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

INPUT DETAILS:
There are four meteors, which strike points (0, 0); (2, 1); (1, 1); and (0, 3) at times 2, 2, 2, and 5, respectively.


                                                                               
    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = meteor impact
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = destroyed pasture
1|. . . . . . .     1|# * * # . . .     1|# # # # . . .   
0|B . . . . . .     0|* # # . . . .     0|# # # . . . .   
  --------------      --------------      -------------- 
  0 1 2 3 4 5 6       0 1 2 3 4 5 6       0 1 2 3 4 5 6 
 

Sample Output 

5

OUTPUT DETAILS:
Examining the plot above at t=5, the closest safe point is (3, 0) -- but Bessie's path to that point is too quickly blocked off by the second meteor. The next closest point is (4,0) -- also blocked too soon. Next closest after that are lattice points on the
(0,5)-(5,0) diagonal. Of those, any one of (0,5), (1,4), and (2,3) is reachable in 5 timeunits.



       5|. . . . . . .   
       4|. . . . . . .   
       3|3 4 5 . . . .    Bessie's locations over time
       2|2 . . . . . .    for one solution
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6  

• 800 submited~ (0) dizem 2009-08-05 19:17:57
• 牛X 本来我还题目读不懂 感谢 (0) vince4053040 2010-02-10 15:40:56