홍수 위험 추정

Mr. Boat는 광활한 토지를 소유하고 있다. 올해 일본에 많은 태풍이 몰아닥쳐 그는 자신의 영지의 홍수 위험을 걱정하게 되었고, 토지의 평균 고도를 알고 싶어 한다. 토지가 너무 넓어 많은 지점에서 고도를 측정할 수는 없다. 영지에 급경사가 없으므로, 제한된 수의 지점에서만 고도를 측정한 뒤 그 값을 바탕으로 나머지 지역의 고도를 근사하면 충분하다고 생각했다.

같은 측정 결과를 바탕으로 여러 근사가 가능할 수 있으며, 그런 경우 그는 최악의 경우, 즉 평균 고도가 가장 낮아지는 근사를 알고 싶어 한다.

직사각형 모양인 Mr. Boat의 영지는 같은 크기의 격자에 맞춰진 직사각형 구역들로 나뉜다. 이 구역들 중 일부에서 고도 측정이 이루어졌고, 측정 결과를 지금 가지고 있다. 나머지 구역의 고도는 변을 공유하는 두 인접 구역의 고도 차이가 최대 1이라는 가정 아래 근사한다.

아래 첫 번째 예에서 토지는 5×4개의 구역으로 나뉜다. (1, 1)과 (5, 4)에 있는 구역의 고도는 각각 10과 3으로 측정되었다. 이 경우 인접한 구역의 고도 차이가 최대 1이라는 가정 아래 모든 구역의 고도가 유일하게 결정된다.

두 번째 예에서는 여러 가능성이 있으며, 그중 평균 고도가 가장 낮아지는 경우를 고려해야 한다.

세 번째 예에서는 고도 차이에 대한 가정을 만족하는 고도 배정이 없다.

여러분의 임무는 그의 영지의 평균 고도를 근사하는 프로그램을 작성하는 것이다. 정확히 말하면, 프로그램은 격자로 나뉜 모든 구역의 근사된 고도와 측정된 고도의 합계를 계산해야 한다. 서로 다른 근사가 둘 이상 가능하면, 프로그램은 가장 가혹한 근사, 즉 고도 합계가 가장 낮아지는 근사로 합계를 계산해야 한다.

입력은 다음과 같은 형식의 단일 테스트 케이스로 이루어진다.

w d n
x1 y1 z1
.
.
.
xn yn zn

여기서 w, d, n은 1 이상 50 이하의 정수이다. w와 d는 토지의 두 변에 있는 구역의 수이다. n은 고도가 측정된 구역의 수이다. 다음 n개 줄의 i번째 줄은 1 ≤ xi ≤ w, 1 ≤ yi ≤ d, −100 ≤ zi ≤ 100을 만족하는 세 정수 xi, yi, zi를 포함한다. 이는 (xi, yi)에 있는 구역의 고도가 zi로 측정되었음을 뜻한다. 같은 구역에 대해 측정 결과는 최대 하나만 주어진다. 즉 i ≠ j이면 (xi, yi) ≠ (xj, yj)이다.

변을 공유하는 두 인접 구역의 고도 차이가 최대 1이라는 가정 아래, 측정되지 않은 모든 구역에 측정된 고도와 충돌 없이 고도를 배정할 수 있으면, 모든 구역의 측정된 고도 또는 근사된 고도의 합계를 정수로 출력한다. 그러한 고도 배정이 둘 이상 가능하면, 가능한 배정 중 고도 합계의 최솟값을 출력한다.

고도 차이 가정을 만족하는 고도 배정이 없으면 No를 출력한다.