Ivica在得到一个送比萨的工作，他所在的城市可以看成是一个R×C的矩形，即从1到R行和1到C列。注意这里交通规则如下，同一行之间可以自由移动，但你要移动到下一行或上一行，则只能从第一列或第C列。Ivica 记下了他在每一个格子里移动需用的时间。每天他有一个送货清单，注意送货时必须按给定的顺序，即使你从某个位置通过，但是按表你不该送到这里，那你也只能以后送这里的货。比萨店在（1，1）处，送货时他中途没有必要返回，送完货也不必返回。
编程计数他送完货后所用的最少时间。
输入：
第一行两个整数R和C (1 ≤ R ≤ 2000, 1 ≤ C ≤ 200), 表示城市的大小。
以下共R行，每行C个整数，表示Ivica通过每个格子所用的时间。时间的范围是 0到5000,包涵边界。
接下来一行一个整数D，表示要送的比萨的个数。 (1 ≤ D ≤ 200 000)。
接下来D行，每行两个整数， A和B (1 ≤ A ≤ R, 1 ≤ B ≤ C),表示要送到的位置。没有一个位置会给两次。
输出：
一个整数，表示最少的送货时间。
70% 的数据， R 最多250.
样例：
输入：
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), [color=red](1, 3)[/color], (2, 3),[color=red] (3, 3)[/color], (2, 3) and [color=red](2, 2)[/color].
总时间：1+2+1+0+1+2+2+2+1+2+3=17.