Problem Background

Returning to dream a cloud dream, what a wonderful dream
Planting flowers, smelling wine, waking and falling asleep, laughing
The vast world, the long journey, the highest peak is stealing half a day of freedom
Occasionally being muddled, not knowing worldly affairs

——Yin Lin & Mu Han, "Cloud Dream Ballad"

Problem Description

"Hey, Goji, you stupid dog, you've been stealing food again! Watch me deal with you!"

Duo Yi stormed out of the courtyard, holding a whisk, while Goji had already disappeared.

The Cloud Dream Court can be considered as a grid array of $n$ rows and $m$ columns, where the grid at the $i$-th row and $j$-th column is denoted as $(i,j)$. Each grid $(i,j)$ either has a height $h_{i,j}$ (where $h_{i,j}$ is a positive integer) or is an obstacle that cannot be passed through. (For convenience, we denote the height of an obstacle as $0$.) Additionally, there are $k$ designated grids in the Cloud Dream Court where flying on a sword is possible. Initially, Duo Yi and Goji are located at grids $(1,1)$ and $(n,m)$, respectively.

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

• Move to one of the adjacent grids $(i-1,j)$, $(i+1,j)$, $(i,j-1)$, or $(i,j+1)$ (cannot move out of the grid boundaries or onto obstacles);
• If grid $(i,j)$ allows flying on a sword, Duo Yi can fly to another grid that also allows flying on a sword and has the same height as grid $(i,j)$;
• Use magic to change the height $h_{i,j}$ of the current grid to any positive integer.

Each of these actions takes $1$ unit of time.

"Hmph, keep running, you stupid dog!" With that, Duo Yi chased after Goji. Duo Yi still needs to continue her training today as soon as possible, so she wants to know the shortest time required to reach grid $(n,m)$.

Input Format

The first line of input contains three integers, representing the number of rows $n$, the number of columns $m$, and the number of grids where flying on a sword is possible $k$, respectively.
The next $n$ lines, each containing $m$ integers, represent the heights $h_{i,j}$ of the grids. It is guaranteed that $h_{1,1}$ and $h_{n,m}$ are not $0$.
The next $k$ lines, each containing two integers $x$ and $y$, represent the coordinates $(x, y)$ of a grid where flying on a sword is allowed. It is guaranteed that these $k$ grids have distinct coordinates.

Output Format

A single integer on one line, representing the minimum time required for Duo Yi to reach grid $(n,m)$. If it is impossible for Duo Yi to reach grid $(n,m)$, output -1.

Sample Input and Output

Input Sample #1

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

Output Sample #1

3

Input Sample #2

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

Output Sample #2

4

Input Sample #3

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

Output Sample #3

7

Input Sample #4

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

Output Sample #4

3

Notes/Hints

Sample 1 Explanation

In the $1$st unit of time, Duo Yi changes the height of the current grid $(1,1)$ to $4$;
In the $2$nd unit of time, Duo Yi flies from grid $(1,1)$ to $(3,4)$;
In the $3$rd unit of time, Duo Yi moves from grid $(3,4)$ to $(4,4)$, catching up with Goji.

Sample 2 Explanation

In the $1$st unit of time, Duo Yi flies from grid $(1,1)$ to $(4,1)$;
In the $2$nd unit of time, Duo Yi moves from grid $(4,1)$ to $(4,2)$;
In the $3$rd unit of time, Duo Yi moves from grid $(4,2)$ to $(4,3)$;
In the $4$th unit of time, Duo Yi moves from grid $(4,3)$ to $(4,4)$, catching up with Goji.

Data Size and Constraints

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

Hints

Please be aware of the impact of large data input on program efficiency and choose an appropriate input method to avoid timeouts.

Notes

This problem has 5 additional sample files, available in the attached dream.zip.

Epilogue

However,别看朵一现在一副生气的样子，可当她追上枸杞后，大抵是不舍得真的动手吧。“嘿嘿，今日的修行结束后，该吃什么好呢？”在这飞瀑悬挂、翠竹怀抱的云梦庭中，修仙炼体，不羡尘嚣，应是这世上最逍遥的事了。

见题面 Input 部分

见题面 Output 部分