Bessie는 특별한 유성우가 온다는 소식을 듣습니다. 유성들은 땅에 충돌하여 맞은 모든 것을 파괴한다고 합니다. 안전이 걱정되어 유성에 영원히 파괴되지 않는 안전한 곳으로 갈 길을 찾기로 합니다. 현재 좌표 평면의 원점에서 풀을 뜯으며, 도중 파괴되지 않고 더 안전한 새로운 곳으로 가려 합니다.

$M$개 유성이 충돌합니다. $(1 \le M \le 50,000)$. 유성 $i$는 시간 $T_{i}$, $(0 \le T_{i} \le 1,000)$에 점 $(X_{i}, Y_{i})$, $(0 \le X_{i} \le 300; 0 \le Y_{i} \le 300)$을 칩니다. 그 점과 상하좌우로 이웃하는 네 격자점을 파괴합니다.

Bessie는 시간 $0$에 원점을 떠나 제1사분면에서 축과 평행하게 초당 거리 한 단위로 아직 파괴되지 않은 인접점(흔히 네 개)으로 갈 수 있습니다. 파괴되는 시간이나 그 이후에는 그 점에 있을 수 없습니다.

안전한 곳까지 걸리는 최소 시간을 구하세요.

입력

표준 입력에서 읽습니다.

• 줄 $1$: 정수 $M$ 하나.

• 줄 $2,\ldots,M+1$: 줄 $i+1$에 공백으로 나눈 세 정수 $X_{i}$, $Y_{i}$, $T_{i}$.

출력

표준 출력에 씁니다.

• 줄 $1$: 최소 시간. 불가능하면 $-1$.

예제

입력 1

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

출력 1

5

참고

네 유성은 $(0, 0)$, $(2, 1)$, $(1, 1)$, $(0, 3)$을 각각 시간 $2$, $2$, $2$, $5$에 칩니다.

    t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = 유성 충돌
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = 파괴된 목초지
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의 위치
       2|2 . . . . . .    한 가지 해의 경우
       1|1 . . . . . .   
       0|0 . . . . . .   
         -------------- 
         0 1 2 3 4 5 6

문제 작성자: Jeffrey Wang, 2007