P6471 [COCI 2008/2009 #6] DOSTAVA

在一个 $r\times c$ 的方格矩阵中，一个快递员从公司 $(1,1)$ 出发，要前往 $d$ 个格子送披萨。在临走的时候，他就已经带上了所有的披萨，这样就不会因为来回奔波而浪费时间了。 快递员任何时刻都只能左右移动，但如果他在第 $1$ 或 $c$ 列时，就可以上下运动。每到一个格子，都有在此处要花费的时间。（多次到达多次计入总时间） 为了能更高效，他想知道，这 $d$ 个送餐点共需要花费多长时间？

输入第一行两个整数 $r,c$，表示矩阵的行和列。 接下来的 $r$ 行，每行 $c$ 个整数，为走到这个格子需要的时长。 接下来一行一个整数 $d$ ，表示总共需要到达的送餐点。 接下来的 $d$ 行，每行两个整数 $a,b$，表示需要送餐到位于第 $a$ 行第 $b$ 列的那一个格子。 虽然快递员要尽量减少用时，但是他**必须按照输入的顺序送餐**，否则会引起顾客的不满。

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

#### 样例 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](https://hsin.hr/coci/archive/2008_2009/) [CONTEST #6](https://hsin.hr/coci/archive/2008_2009/contest6_tasks.pdf) *T5 DOSTAVA***。