Minimal Maximum Move Cost for Key Extraction

Mori finds himself trapped on a deserted island where Princess Soha is being held captive in the dungeon. The dungeon is protected by an ancient magic array – an M × N grid where each cell has its own height. Some cells have keys buried in them, but Mori cannot extract the key directly. Instead, for each key cell he must cast a spell by walking a simple path that starts at the key cell and covers T distinct cells (including the starting cell). During this movement, the stamina cost to go from one cell to an adjacent cell is the absolute difference of their heights. The difficulty value P for a key cell is defined as the maximum stamina cost of any move along the chosen path. Mori wants to minimize the difficulty value for each key cell so that the sum over all key cells is as small as possible.

Your task is to help Mori determine the minimum possible sum of difficulty values for all key cells. For each key cell, you must choose a simple path of exactly T cells (starting from that key cell) so that the maximum cost (i.e. the maximum absolute difference between heights in any step along that path) is as low as possible, and then sum these minimal values over all key cells.

Note: Movement is allowed only in the four cardinal directions: up, down, left, and right.

Mathematical formulation: For a path a₁, a₂, ..., a_T starting at a buried key (a₁), let the cost of moving between adjacent cells be c_i = |height(a_i) - height(a_i+1)| for 1 ≤ i < T. The difficulty value for that key cell is P = min{ max(c₁, c₂, ..., c_T-1) } taken over all simple paths of length T. The goal is to compute the sum of these minimal P values for all key cells.

inputFormat

The first line contains three integers M, N, and T (1 ≤ M, N ≤ 10, T ≥ 1), representing the number of rows, columns, and the required number of cells in the spell‐casting path.

The next M lines each contain N integers representing the height of each cell in the grid.

The following M lines each contain N integers (either 0 or 1); a 1 indicates that a key is buried in that cell, and 0 indicates otherwise.

outputFormat

Output a single integer – the minimum possible sum of the difficulty values (i.e. the minimal maximum move costs) for all key cells.

sample

3 3 3
1 2 3
4 5 6
7 8 9
1 0 1
0 1 0
1 0 0

6