题目背景

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

——银临 & 慕寒《云梦谣》

题目描述

“喂，枸杞，你这只笨狗，又偷吃！看我不收拾你！”

朵一气呼呼地从院子里跑出来，手中握着掸子，而枸杞早已不见踪影。

云梦庭可以看作一个 $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。

后记

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