스키 코스 평가

겨울 올림픽의 크로스컨트리 스키 코스는 M x N 그리드의 고도(1 <= M,N <= 500)로 설명되며, 각 고도는 0에서 1,000,000,000의 범위에 있습니다.

이 그리드의 일부 셀은 코스의 시작점으로 지정되어 있습니다. 올림픽 주최자들은 각 시작점에 난이도 등급을 할당하려고 합니다. 시작점 P의 난이도는 스키어가 P에서 시작하여 그리드의 적어도 T개의 셀(1 <= T <= MN)을 성공적으로 도달할 수 있도록 하는 D의 최소 가능 값을 가져야 합니다. 스키어는 셀 간의 고도 차이가 D를 초과하지 않는 경우에만 인접한 셀로 이동할 수 있습니다. 두 셀은 한쪽이 다른 쪽의 북쪽, 남쪽, 동쪽, 또는 서쪽에 직접 위치하면 인접합니다.

문제는 주최자들이 각 시작점의 난이도 등급을 계산하는 것을 돕는 것입니다.

• 1번째 줄: 정수 M, N 및 T.
• 2번째 줄..1+M번째 줄: 이 M개의 줄 각각은 N개의 정수 고도를 포함합니다.
• 2+M번째 줄..1+2M번째 줄 : 이 M개의 줄 각각은 0 또는 1인 N개의 값을 포함합니다. 여기서 1은 출발점인 셀을 나타냅니다.

• 1번째 줄: 모든 시작점의 난이도 등급의 합 (각각의 난이도 등급은 32비트 정수에 들어가지 않을 수 있음에 유의하십시오).