스키 코스 난이도

겨울 무림픽의 크로스컨트리 스키 코스는 $M \times N$ 크기의 고도 격자로 주어진다. $1 \le M, N \le 500$이고, 각 칸의 고도는 $0$ 이상 $10^9$ 이하인 정수이다.

격자의 몇몇 칸은 코스의 출발점으로 지정되어 있다. 조직위원회는 출발점마다 난이도를 매기려고 한다. 출발점 $P$의 난이도는 다음 조건을 만족하는 가장 작은 $D$이다. 소가 $P$에서 출발해 고도 차이의 절댓값이 $D$ 이하인 인접한 칸으로만 이동할 때, $P$ 자신을 포함해 서로 다른 칸 $T$개 이상에 도달할 수 있어야 한다. 여기서 $1 \le T \le MN$이다. 두 칸은 한쪽이 다른 쪽의 바로 북쪽, 남쪽, 동쪽, 서쪽에 있을 때 인접하다고 한다.

출발점마다 난이도를 계산해 조직위원회를 도와라.

• 첫째 줄에 정수 $M$, $N$, $T$가 주어진다.
• 다음 $M$개 줄에는 줄마다 $N$개의 고도가 주어진다.
• 그다음 $M$개 줄에는 줄마다 $N$개의 값이 주어진다. 각 값은 $0$ 또는 $1$이고, $1$은 그 칸이 출발점이라는 뜻이다.

• 첫째 줄에 모든 출발점의 난이도를 더한 값을 출력한다. 난이도 하나하나는 32비트 정수에 들어가지만, 그 합은 들어가지 않을 수 있다.

입력 설명

스키 코스는 $3 \times 5$ 크기의 고도 격자이다. 왼쪽 위 칸과 오른쪽 아래 칸이 출발점이고, 각 출발점에서 칸 $10$개 이상에 도달해야 한다.

출력 설명

왼쪽 위 출발점의 난이도는 $4$, 오른쪽 아래 출발점의 난이도는 $20$이다.