编程题：最短路径

小艾维卡最近找到了一份工作，为城里最受欢迎的披萨店送披萨。

在工作日开始时，他会收到一份清单，上面列出了他需要将披萨送到的地点，并按这些地点的顺序排列。

这座城市被划分为R×C单元。行编号为1到R，列编号为1到C。

从每一个方格，都有可能移动到左右相邻的方格。只允许在第一列和最后一列（第1列和第C列）中向上或向下移动。

披萨店在左上角（1，1），这是Ivica的起点。伊维卡带着他当天要送的所有披萨，这样他就不必在两次送披萨之间或最后一次送披萨之后回到披萨店。

对于城市中的每个位置，艾维卡都知道他每次在里面会花多少时间（例如，试图通过十字路口）。

编写一个程序，计算Ivica交付所有披萨的最小时间

### 输入格式:
第一行包含整数R和C（1≤R≤2000, 1≤C≤200） 表示这座城市的规模。

下面的每一行都包含C整数。这是艾维卡每次进入一个地点的时间。时间将是0到5000之间的整数，包括0和5000。

下一行包含一个整数D（1≤D≤200000），表示这是当天送披萨的数量。

以下D行中的每一行都包含两个整数A和B（1≤A≤ R，1≤B≤C），披萨必须送达的地点。披萨是按一定的顺序送的。不会连续两次给出相同的位置。

### 输出格式:
以最短的时间为依维卡提供所有披萨。

### 输入样例1:
in
3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2


### 输出样例1:
out
17


### 输入样例2:
in
2 5
0 0 0 0 0
1 4 2 3 2
4
1 5
2 2
2 5
2 1


### 输出样例2:
out
9


在第一个示例中，最短路径通过以下位置：
（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






答案：若无答案欢迎评论