[요약 중 ] 소 올림픽에서 크로스 컨트리 종목은 M x N 그리드 모양이 고지로 표현된다.(1 <= M,N <= 500), 각 고지의 높은 0 에서 1,000,000,000 이다.

이 격자의 어떤 셀들은 이 코스의 시작 지점으로 표시되었다. 올림픽 관계자들은 각 시점지점에 난이도를 표시하려고 한다.

The difficulty level of a starting point P should be the minimum possible value of D such that a cow can successfully reach at least T total cells of the grid (1 <= T <= MN), if she starts at P and can only move from cell to adjacent cell if the absolute difference in elevation between the cells is at most D.

시작 지점 P 의 난이도레벨은 가능한 D 의 최소 값이다. 소가 연속적으로 적어도 T 전체 셀을 방문할 수 도착할 수 있다 그리의의 전체 만약 시작지점 P 에서 시작하여 인접한 셀들로 이동할 수 있따. 만약 고지의 절대값의 차가 많아야 D 이면

두 셀이 동서남북으로 연결되면 인접하다고 한다.

시작 지점의 난이도를 계산하는 것을 도우는 것이 문제이다.

Some of the cells in this grid are designated as starting points for the course. The organizers of the Moolympics want to assign a difficulty rating to each starting point.

The difficulty level of a starting point P should be the minimum possible value of D such that a cow can successfully reach at least T total cells of the grid (1 <= T <= MN), if she starts at P and can only move from cell to adjacent cell if the absolute difference in elevation between the cells is at most D.

Two cells are adjacent if one is directly north, south, east, or west of the other.

Please help the organizers compute the difficulty rating for each starting point.

입력

• Line 1: The integers M, N, and T.
• Lines 2..1+M: Each of these M lines contains N integer elevations.
• Lines 2+M..1+2M: Each of these M lines contains N values that are either 0 or 1, with 1 indicating a cell that is a starting point.

출력

입출력 예

입력

3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1

출력

24

입출력 보충

The ski course is described by a 3 x 5 grid of elevations. The upper-left and lower-right cells are designated as starting points. From each starting point, we must be able to reach at least 10 cells.

OUTPUT DETAILS:

The difficulty rating of the upper-left starting point is 4, and for the lower-right it is 20.

출처:2014/jan/gold