SP4034 MDOSTAVA - Pizza Delivery
题目描述
FarmerJohn 最近得到了一份工作，那就是送肯德基外卖！
FJ 所在的小镇可以看作是一个 $R$ 行 $C$ 列的矩形，被划分成 $R\times C$ 个单元格子，从上往下，行的编号是 $1\sim R$，而从左往右，列的编号是 $1\sim C$。
FJ 一开始在第 $1$ 行第 $1$ 列的格子处，他收到 $D$ 个顾客的订单，第 $i$ 个顾客的位置在第 $R_i$ 行第 $C_i$ 列的格子。
FJ 一开始就把所有顾客的订餐一起装在背包里，这样在送餐过程中就无须送一次餐返回一次出发点了。FJ 必须严格按照次序给顾客送肯德基（即先送完第 $1$ 个顾客，再送第 $2$ 个顾客，依次类推）。当送完所有的肯德基外卖后，FJ 也没有必要返回出发处。
FJ 的移动规则是这样的：他可以从当前格子移动一步，到达相邻的左格子或者相邻的右格子（两个格子相邻是指它们有公共边）。 **特别的，如果 FJ 当前所在格的列是第 $1$ 列或者第 $C$ 列，那么 FJ 还可以向上移动一格或者向下移动一格。**
任意时刻，FJ 都不能走出矩形的边界。FJ 每试图进入一个格子，都会花费一定的时间 $t_{i,j}$。在不同的格子，$t_{i,j}$ 可能不同。现在 FJ 要去装订餐了，所以问你：他送完所有订餐，至少需要多少时间？
输入格式
第一行，两个整数，$R$ 和 $C$。
接下来有 $R$ 行 $C$ 列，第 $i$ 行第 $j$ 列的整数表示 FJ 若试图进入格子 $(i,j)$ ，花费的时间 $t_{i,j}$。
接下来一行，有一个整数 $D$，表示有 $D$ 个顾客订餐。
接下来有 $D$ 行，每行两个整数，依次表示顾客的位置，即其所在行和所在列。保证顾客所在的位置不会重复。
输出格式
一个整数，表示 FJ 送完所有订餐的最少时间。
#### 数据范围与约定
$1\le R\le 2000,1\le C\le 200,1\le D\le 200000,0\le T\le 5000。$
#### 输入输出样例
输入 #1：
```
3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2
```
输出 #1：
```
17
```
输入 #2：
```
2 5
0 0 0 0 0
1 4 2 3 2
4
1 5
2 2
2 5
2 1
```
输出 #1：
```
9
```
Translated by @[Vocaloid世末歌者](https://www.luogu.com.cn/user/678881).