Description

But good days did not last. Mori’s great general, the Demon Hunter, betrayed him at this moment, proclaimed himself king, rallied the dragons hidden in the Axis of the World to rebel, and abducted Princess Soha. In the battle against the Demon Hunter, Mori was besieged and trapped on a deserted, uninhabited island. However, after scouting, he was pleasantly surprised to discover that Soha had also been imprisoned by the Demon Hunter on this very island.

After careful study, Mori found that the dungeon holding Soha required several keys to open, and the keys were buried within a series of magic arrays. By virtue of his skills and magic, Mori can break the arrays and obtain the keys. The magic array is a matrix of size $M\times N$, and each cell of the array has its own height. Some cells have keys buried in them, but Mori’s magic is insufficient to dig them out directly. He discovered that if he starts from a cell that has a buried key and walks to adjacent cells (up, down, left, right), and casts spells on at least $T$ distinct cells (including the key cell itself), he can dig out the key. In other words, before digging each key, he must start from the cell with the key and then visit $T-1$ other distinct cells.

Although casting spells costs no stamina, moving costs a certain amount of stamina (failed PE, 233). The stamina cost to move from one cell to another is the absolute difference between the height values of the two cells.

For each cell that contains a key, define its difficulty value $P$ as the maximum stamina cost among all moves between cells during the casting process.

Mori wants this difficulty value to be as small as possible. Only by conserving enough stamina can he rescue Soha, and together they can defeat the treacherous Demon Hunter.

So, he wants to know the minimum possible sum of the difficulty values over all cells that contain keys.

Input Format

The first line contains three integers $M$, $N$, and $T$.

The next $M$ lines each contain $N$ integers, giving the height of each cell.

The next $M$ lines each contain $N$ integers $0$ or $1$, where $1$ means the cell contains a buried key.

Output Format

Output a single integer, the minimum possible sum of difficulty values.

3 5 5
20 21 20 20 21
19 22 20 60 80
80 90 80 70 90
1 0 0 0 0
0 0 0 0 0
1 0 0 0 1

31

Hint

$1 ≤ M, N ≤ 600$

$1 ≤ T ≤ M\times N$

Translated by ChatGPT 5