题目描述

在一个 $r\times c$ 的方格矩阵中，一个快递员从公司 $(1,1)$ 出发，要前往 $d$ 个格子送披萨。在临走的时候，他就已经带上了所有的披萨，这样就不会因为来回奔波而浪费时间了。

快递员任何时刻都只能左右移动，但如果他在第 $1$ 或 $c$ 列时，就可以上下运动。每到一个格子，都有在此处要花费的时间。（多次到达多次计入总时间）

为了能更高效，他想知道，这 $d$ 个送餐点共需要花费多长时间？

输入格式

输入第一行两个整数 $r,c$，表示矩阵的行和列。

接下来的 $r$ 行，每行 $c$ 个整数，为走到这个格子需要的时长。

接下来一行一个整数 $d$ ，表示总共需要到达的送餐点。

接下来的 $d$ 行，每行两个整数 $a,b$，表示需要送餐到位于第 $a$ 行第 $b$ 列的那一个格子。

虽然快递员要尽量减少用时，但是他必须按照输入的顺序送餐，否则会引起顾客的不满。

输出格式

输出一行一个整数，表示最少的送餐时间。

3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2

17

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

9

提示

样例 1 解释

最短的送餐路线为：

$(1,1),(2,1),(3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (2, 3), (3, 3), (2, 3),(2, 2)$。

总用时为：$1+2+1+0+1+2+2+2+1+2+3=17$。

数据规模与约定

• 对于 $70\%$ 的数据，保证 $r\le 250$；
• 对于 $100\%$ 的数据，保证 $1\le r\le 2000$，$1\le c\le 200$，$1\le d\le 2\times 10^5$，$1\le a\le r$，$1\le b\le c$。

说明

题目译自 COCI2008-2009 CONTEST #6 T5 DOSTAVA。