Background

Come back and have a Yunmeng dream, a great dream is good.
Plant flowers and smell the wine, wake up, get drunk, laugh and smile.
The world is vast, the road back is long and the mountains are high; the rarest thing is to steal half a day of leisure.
Sometimes be confused, do not ask about worldly affairs, and do not know.

— Yin Lin & Mu Han, Yunmeng Ballad

Problem Description

“Hey, Gouqi, you silly dog, you’re stealing food again! Watch me teach you a lesson!”

Duo Yi ran out of the yard angrily, holding a duster, but Gouqi had already disappeared.

Yunmeng Courtyard can be seen as a grid of $n$ rows and $m$ columns. The cell in row $i$ and column $j$ is denoted as $(i,j)$. Each cell $(i,j)$ either has a height $h_{i,j}$ (where $h_{i,j}$ is a positive integer), or it is an obstacle and cannot be passed through. (For convenience, we define that an obstacle has $h_{i,j}$ equal to $0$.) In addition, there are $k$ designated cells in Yunmeng Courtyard where sword flight is allowed. Initially, Duo Yi and Gouqi are located at cells $(1,1)$ and $(n,m)$ respectively.

Duo Yi is not very skilled at sword flight yet, and she cannot control the flying height well. Therefore, at any moment, when Duo Yi is on cell $(i,j)$, she can perform one of the following actions:

• Move to one of the adjacent cells $(i-1,j)$, $(i+1,j)$, $(i,j-1)$, $(i,j+1)$ (she cannot move outside the grid, and cannot move onto an obstacle).
• If sword flight is allowed on cell $(i,j)$, then Duo Yi can fly to another cell that also allows sword flight and has the same height as cell $(i,j)$.
• Use immortal magic to change the height $h_{i,j}$ of the current cell to any positive integer.

Each action above costs $1$ unit of time.

“Hmph, you silly dog, keep running!” After saying that, Duo Yi chased after him. Duo Yi still needs to continue today’s cultivation as soon as possible, so she wants to know the minimum time needed to reach cell $(n,m)$.

Input Format

The first line contains three integers, which are the number of rows $n$, the number of columns $m$, and the number of cells where sword flight is allowed $k$.
Then follow $n$ lines, each containing $m$ integers. The $j$-th number in the $i$-th line represents the height $h_{i,j}$ of cell $(i,j)$. The data guarantees that $h_{1,1}$ and $h_{n,m}$ are not $0$.
Then follow $k$ lines, each containing two integers $x$ and $y$, representing the coordinates $(x, y)$ of a cell where sword flight is allowed. The data guarantees that these $k$ cells have pairwise distinct coordinates.

Output Format

Output one integer in a single line, indicating the minimum time needed for Duo Yi to reach $(n,m)$. If Duo Yi cannot reach it, output -1.

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

3

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

4

2 5 0
1 0 3 3 4
2 3 4 0 5

7

4 4 3
1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1
1 1
2 1
3 3

3

Hint

Sample 1 Explanation

In the $1$-st unit of time, Duo Yi changes the height of the current cell $(1,1)$ to $4$.
In the $2$-nd unit of time, Duo Yi flies from cell $(1,1)$ to $(3,4)$ by sword flight.
In the $3$-rd unit of time, Duo Yi moves from cell $(3,4)$ to $(4,4)$ and catches up with Gouqi.

Sample 2 Explanation

In the $1$-st unit of time, Duo Yi flies from cell $(1,1)$ to $(4,1)$ by sword flight.
In the $2$-nd unit of time, Duo Yi moves from cell $(4,1)$ to $(4,2)$.
In the $3$-rd unit of time, Duo Yi moves from cell $(4,2)$ to $(4,3)$.
In the $4$-th unit of time, Duo Yi moves from cell $(4,3)$ to $(4,4)$ and catches up with Gouqi.

Constraints

For all test points, it is guaranteed that $1 \leq n, m \leq 3 \times 10^3$, $0 \leq k,h_{i,j} \leq n \times m$.

Notes

Please pay attention to the impact of large input on program efficiency. Choose an appropriate input method to avoid TLE.

Additional Information

This problem has 5 additional sample files. See dream.zip in the attachments.

Epilogue

However, even though Duo Yi looks angry now, after she catches up with Gouqi, she probably will not really have the heart to hit him. “Hehe, after today’s cultivation ends, what should I eat?” In Yunmeng Courtyard, with waterfalls hanging down and green bamboo all around, cultivating and training the body without envying worldly noise should be the most carefree thing in the world.

Translated by ChatGPT 5