Cross Country Skiing

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

Some cells of the grid are marked as waypoints. The organizers want to give the whole course a difficulty rating $D$ so that a cow can get from any waypoint to any other waypoint by repeatedly skiing from a cell to an adjacent cell whose elevation differs by at most $D$ in absolute value. Two cells are adjacent when one is directly north, south, east, or west of the other. The difficulty rating of the course is the smallest $D$ for which all waypoints are mutually reachable.

If the course has fewer than two waypoints, the difficulty rating is $0$.

• Line 1: the integers $M$ and $N$.
• Lines 2 to $1+M$: each line has $N$ integer elevations.
• Lines $2+M$ to $1+2M$: each line has $N$ values, each either $0$ or $1$. A $1$ marks a waypoint.

• Line 1: the difficulty rating of the course, the smallest $D$ that keeps every waypoint reachable from every other waypoint.

The first example describes a $3 \times 5$ grid. The upper-left, upper-right, and lower-right cells are waypoints.

With $D = 21$ the three waypoints reach each other. With any $D$ smaller than $21$, the upper-right waypoint cannot be reached from the other two.