小 Ivica 最近在镇上最受欢迎的比萨店找到了一份送比萨的工作。

在工作日开始时，他会收到一张需要送达比萨的地点列表，送货顺序与列表中给出的顺序相同。

城市被划分为 $R \times C$ 的网格。行从 $1$ 到 $R$ 编号，列从 $1$ 到 $C$ 编号。

从任意单元格出发，都可以移动到其左侧和右侧的相邻单元格。只有在第一列和最后一列（第 $1$ 列和第 $C$ 列）中才允许向上或向下移动。

比萨店位于左上角 $(1, 1)$，这也是 Ivica 出发的起点。Ivica 会带上当天要配送的所有比萨，因此在两次配送之间或最后一次配送之后，他不需要返回比萨店。

对于城市中的每个位置，Ivica 都知道他每次经过该位置时需要花费的时间（例如，通过十字路口所需的时间）。

编写一个程序，计算 Ivica 送完所有比萨所需的最短时间。

输入格式

第一行包含两个整数 $R$ 和 $C$（$1 \le R \le 2000$，$1 \le C \le 200$），表示城市的尺寸。

接下来的 $R$ 行，每行包含 $C$ 个整数。这些是 Ivica 每次进入某个位置时所花费的时间。时间为 $0$ 到 $5000$ 之间（含 $0$ 和 $5000$）的整数。

下一行包含一个整数 $D$（$1 \le D \le 200000$），表示当天需要配送的比萨数量。

接下来的 $D$ 行，每行包含两个整数 $A$ 和 $B$（$1 \le A \le R$，$1 \le B \le C$），表示需要送达比萨的位置。比萨按必须送达的顺序给出。不会有连续两个相同的送货位置。

输出格式

输出 Ivica 送完所有比萨所需的最短时间。

子任务

在占总分 70% 的测试数据中，$R$ 最大为 $250$。

样例

输入 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

输出 2

9

说明

在第一个样例中，最短路径经过以下位置： $(1, 1)$，$(2, 1)$，$(3, 1)$，$(3, 2)$，$(3, 3)$，$(2, 3)$，$(1, 3)$，$(2, 3)$，$(3, 3)$，$(2, 3)$ 和 $(2, 2)$。

加粗的位置表示 Ivica 进行配送的地点。

配送的总时间为 $1+2+1+0+1+2+2+2+1+2+3=17$。