Minimum Difficulty for Rally Track Connectivity

In Boai City, a car rally race is about to be held on a rugged terrain. The terrain is described as an $N \times M$ grid, where each cell represents the elevation of that part of the terrain. The elevation of each cell is an integer between $0$ and $10^9$. Some of these cells are designated as road signs. The organizers want to assign a difficulty level $D$ for the entire route such that for any two road signs, there exists a path connecting them where the elevation difference between any two adjacent cells in the path does not exceed $D$. Adjacency is defined in the four cardinal directions (north, south, east, west). Your task is to determine the minimum $D$ required so that all road signs are mutually reachable under the given condition.

Formally, given an $N \times M$ grid of integers representing the elevations and a list of $K$ road sign coordinates, find the minimum integer $D$ such that for every pair of road sign cells, there exists a path between them where for every two adjacent cells on the path with elevations $a$ and $b$, the condition (|a - b| \leq D) holds.

Note:

• If there is only one road sign, output 0.

inputFormat

The input is given in the following format:

N M
<grid with N rows and M columns of integers>
K
<K lines each with two integers r and c (1-indexed coordinates of a road sign)&

Where:

• 1 ≤ N, M ≤ 500.
• Each elevation is an integer from 0 to 10⁹.
• 1 ≤ K ≤ N*M.

outputFormat

Output a single integer: the minimum difficulty value $D$ such that for any two road sign cells, there exists a path between them where the difference in elevation between any two adjacent cells does not exceed $D$.

sample

3 3
1 2 1
3 10 3
1 2 1
4
1 1
1 3
3 1
3 3

2