26009번 - 험난한 등굣길

문제

통학러 재헌이는 1교시 수업을 듣기 위해 아침 일찍 학교에 가려고 한다. 재헌이가 사는 지역은 크기가 $N \times M$ 인 격자로 나타낼 수 있는데, $i$행 $j$열에 해당하는 칸을 $(i, j)$로 나타낼 때 재헌이는 현재 $(1, 1)$에, 학교는 $(N, M)$에 위치해 있다. 재헌이는 상하좌우로 한 칸씩 이동할 수 있고 지역 바깥으로 나갈 수는 없다.

등굣길은 순탄치만은 않은데, 이 지역에는 $K$개의 정체 구역이 있다. $i$번째 정체 구역은 세 정수 $R_i, C_i, D_i$로 표현되며, 이는 $(R_i, C_i)$로부터 거리가 $D_i$ 이하인 칸들에는 극심한 교통 정체가 일어나고 있음을 의미한다. 두 칸 $(R_1, C_1), (R_2, C_2)$ 사이의 거리는 $|R_1 - R_2| + |C_1 - C_2|$와 같다.

재헌이는 교통 정체가 일어나고 있는 칸을 방문하면 수업에 지각하게 되며, 방문하지 않는다면 지각하지 않고 무사히 수업을 들을 수 있다. $K$개의 정체 구역에 대한 정보가 주어졌을 때 재헌이가 지각하지 않고 1교시 수업을 들을 수 있을지 알아보자. 또한 재헌이는 최대한 일찍 학교에 도착하려 하기 때문에, 만약 재헌이가 지각하지 않고 수업을 들을 수 있다면 최소 몇 번의 이동으로 수업을 들으러 갈 수 있는지도 구해보자.

입력

첫째 줄에 격자의 크기 $N, M$이 주어진다. $(2 \le N, M \le 3\ 000)$

다음 줄에 정체 구역의 수 $K$가 주어진다. $(1 \le K \le 3\ 000)$

다음 $K$개 줄에 걸쳐 각 정체 구역의 정보 $R_i, C_i, D_i$가 주어진다. $(1 \le R_i \le N, 1 \le C_i \le M, 0 \le D_i \le 3\ 000)$

$(1, 1)$ 또는 $(N, M)$에 교통 정체가 일어나고 있는 경우는 주어지지 않는다.

출력

재헌이가 지각하지 않고 수업을 들을 수 있으면 YES를 출력하고, 다음 줄에 최소 이동 횟수를 출력한다.

만약 지각하지 않고 수업을 들을 수 없다면 NO를 출력한다.

제한

힌트