[yLOI2023] 云梦谣

> 归来且做云梦梦一场 大梦好 > 栽花闻酒香 醒醒醉醉笑笑 > 天地偌大复路远山高 最难得偷半日逍遥 > 偶尔糊涂不问世事不知晓 ——银临 & 慕寒《云梦谣》

“喂，枸杞，你这只笨狗，又偷吃！看我不收拾你！” 朵一气呼呼地从院子里跑出来，手中握着掸子，而枸杞早已不见踪影。 云梦庭可以看作一个 $n$ 行 $m$ 列的方格阵，第 $i$ 行第 $j$ 列的格子被记作 $(i,j)$。每个格子 $(i,j)$ 要么有一个高度 $h_{i,j}$（$h_{i,j}$ 为正整数），要么是障碍物，不能通过。（方便起见，约定障碍物的 $h_{i,j}$ 用 $0$ 表示。）另外，云梦庭上有 $k$ 个指定的格子上可以进行**御剑飞行**。开始时，朵一和枸杞分别位于方格 $(1,1)$ 和 $(n,m)$。 朵一的御剑飞行还不是很熟练，现在她还控制不好御剑的高度。因此在任意时刻，朵一在方格 $(i,j)$ 上可以做如下行动之一： - 移动到与该方格相邻的方格 $(i-1,j)$、$(i+1,j)$、$(i,j-1)$、$(i,j+1)$ 之一上（不能移动出方格边界，也不能移动到障碍物上）； - 如果方格 $(i,j)$ 上允许御剑飞行，则朵一可以御剑飞行至另一个**同样允许御剑飞行且与方格 $(i,j)$ 高度相等的方格上**； - 使用仙法将当前格子的高度 $h_{i,j}$ 改变为任一正整数。 进行上述每项行动均需花费 $1$ 个单位时间。 “哼，笨狗子你再跑！”说罢，朵一便追了出去。朵一接下来还要尽快继续今天的修行，因此她想知道到达 $(n,m)$ 格子所需的最短时间是多少。

输入的第一行有三个整数，依次表示方格阵的行数 $n$、列数 $m$ 和能御剑飞行的方格个数 $k$。 接下来 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数表示方格 $(i,j)$ 的高度 $h_{i,j}$。数据保证 $h_{1,1}$ 和 $h_{n,m}$ 不为 $0$。 接下来 $k$ 行，每行两个整数 $x$ 和 $y$，表示一个允许御剑飞行的方格的坐标 $(x, y)$。数据保证这 $k$ 个方格的坐标互不相同。

一行一个整数，表示朵一到达 $(n,m)$ 所需的最小时间。如果朵一无法到达，输出 ```-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

### 样例 1 解释 第 $1$ 个单位时间，朵一将当前方格 $(1,1)$ 的高度修改为 $4$； 第 $2$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(3,4)$； 第 $3$ 个单位时间，朵一从方格 $(3,4)$ 移动到 $(4,4)$，追上了枸杞。 ### 样例 2 解释 第 $1$ 个单位时间，朵一从方格 $(1,1)$ 御剑飞行至 $(4,1)$； 第 $2$ 个单位时间，朵一从方格 $(4,1)$ 移动到 $(4,2)$； 第 $3$ 个单位时间，朵一从方格 $(4,2)$ 移动到 $(4,3)$； 第 $4$ 个单位时间，朵一从方格 $(4,3)$ 移动到 $(4,4)$，追上了枸杞。 ### 数据规模与约定  对全部的测试点，保证 $1 \leq n, m \leq 3 \times 10^3$，$0 \leq k,h_{i,j} \leq n \times m$。 ### 提示 请注意大量数据读入对程序效率造成的影响，选择合适的读入方式，避免超时。 ### 说明 本题共有 5 个附加样例文件，见附件里的 dream.zip。 ### 后记 不过，别看朵一现在一副生气的样子，可当她追上枸杞后，大抵是不舍得真的动手吧。“嘿嘿，今日的修行结束后，该吃什么好呢？”在这飞瀑悬挂、翠竹怀抱的云梦庭中，修仙炼体，不羡尘嚣，应是这世上最逍遥的事了。