유성우 | cho.sh

문제

베시(Bessie)는 엄청난 유성우가 다가온다는 소식을 들었다. 보도에 따르면 유성들은 때리는 모든 것을 파괴한다. 안전이 걱정된 베시는 어떤 유성에도 절대 파괴되지 않는 안전한 지점으로 대피하기로 한다.

베시는 좌표평면의 원점 $(0, 0)$에서 풀을 뜯고 있으며, 도중에 유성을 피하면서 더 안전한 곳으로 이동하려고 한다.

유성은 모두 $M$개가 떨어진다. $i$번째 유성은 시각 $T_i$에 점 $(X_i, Y_i)$에 충돌한다. 각 유성은 충돌한 점과 그 점에 상하좌우로 인접한 네 개의 격자점을 함께 파괴한다.

베시는 시각 $0$에 원점을 출발한다. 그녀는 제1사분면(모든 좌표가 $0$ 이상)에서만 움직이며, 축에 평행하게 초당 거리 $1$의 속도로 아직 파괴되지 않은 인접한 격자점으로 이동한다. 어떤 점이 파괴되는 시각과 같거나 그보다 늦은 시각에는 그 점에 머물 수 없다.

베시가 안전한 지점에 도달하는 데 걸리는 최소 시간을 구하여라. 도달이 불가능하면 그 사실을 보고한다.

제약: $1 \le M \le 50000$, $0 \le X_i \le 300$, $0 \le Y_i \le 300$, $0 \le T_i \le 1000$.

입력

1번째 줄: 정수 $M$ 하나.
2번째 줄부터 $M+1$번째 줄까지: $i+1$번째 줄에는 세 정수 $X_i$, $Y_i$, $T_i$가 공백으로 구분되어 주어진다.

출력

1번째 줄: 베시가 안전한 지점에 도달하는 최소 시간. 도달이 불가능하면 $-1$을 출력한다.

힌트

예시에서는 네 개의 유성이 각각 점 $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$에 시각 $2$, $2$, $2$, $5$에 충돌한다.

    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

$t = 5$일 때 가장 가까운 안전한 점은 $(3, 0)$이지만, 그리로 가는 경로는 두 번째 유성에 의해 너무 빨리 막힌다. 그 다음으로 가까운 $(4, 0)$ 또한 너무 일찍 막힌다. 그 다음은 $(0, 5)$에서 $(5, 0)$까지의 대각선 위 격자점들이며, 그중 $(0, 5)$, $(1, 4)$, $(2, 3)$ 중 아무 것이나 $5$의 시간에 도달할 수 있다.

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