Ski Course Rating

The cross-country skiing course at the winter Moolympics is given as an $M \times N$ grid of elevations, with $1 \le M, N \le 500$. Every elevation is an integer between $0$ and $10^9$.

Some cells of the grid are marked as starting points of the course. The organizers want to give each starting point a difficulty rating. The difficulty rating of a starting point $P$ is the smallest $D$ such that a cow who starts at $P$ reaches at least $T$ cells in total, counting $P$ itself, when she may only step between adjacent cells whose elevations differ by at most $D$. Here $1 \le T \le MN$. Two cells are adjacent when one lies directly north, south, east, or west of the other.

Compute the difficulty rating of every starting point and help the organizers.

• Line 1: the integers $M$, $N$, and $T$.
• Lines $2$ to $1 + M$: each line holds $N$ integer elevations.
• Lines $2 + M$ to $1 + 2M$: each line holds $N$ values, each of them $0$ or $1$. A $1$ marks a cell that is a starting point.

• Line 1: the sum of the difficulty ratings of all starting points. A single rating fits in a 32-bit integer, but the sum may not.

Input details

The ski course is a $3 \times 5$ grid of elevations. The upper-left cell and the lower-right cell are starting points, and from each starting point the cow must reach at least $10$ cells.

Output details

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