A1624.狗星邮电科技大学

AC狗上大学后，为了赚点必要的生活费（原因是之前买狗星农工科技公司的股票赔光了），找了份兼职，给寝室楼里不愿意去食堂吃饭的同学送外卖。

狗星邮电科技大学的寝室楼布局是这样的，最左右两边各一个楼梯，中间是每个寝室，寝室门口一条长廊。

大概是这个样子。

由于这些学生不讲卫生，导致走廊里堆满了杂物，通过每个寝室门前的走廊区域都要耗费不少时间。

上下楼层只能走两侧楼梯。

现在AC狗已经带上了所有要送的外卖，按照下单顺序给他们送外卖，请帮他计算他最少要花费多少时间？

输入的第一行为两个整数 $N,M$，代表寝室楼共 $N$ 层， $M$ 列。

第 $1$ 列和第 $M$ 列是楼梯。

接下来的 $N$ 行，每行 $M$ 个整数，代表穿越这个房间门口的走廊所需的时间。

接下来一行为一个整数 $T$，代表有 $T$ 份订单。输入顺序为下单顺序。

接下来 $T$ 行，每行两个整数，代表这份订单送往的位置。

输出为一个整数，代表送餐的最短时间。

【样例解释】

起点为(1,1)，一共有三份外卖，按照下单顺序分别在 (1,3),(3,3),(2,2)。

最短送餐时间的顺序为

(1,1)-->(2,1)-->(3, 1)-->(3, 2)-->(3, 3)-->(2, 3)-->(1, 3)-->(2, 3)-->(3, 3)-->(2, 3)-->(2, 2)

【数据规模】

对于百分百的数据

$1\le N\le 2000$

$1\le M\le 200$

$1\le T\le 2\times 10^5$