A1624.狗星邮电科技大学

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

大概是这个样子。

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

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

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

输入格式

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

11 列和第 MM 列是楼梯。

接下来的 NN 行,每行 MM 个整数,代表穿越这个房间门口的走廊所需的时间。

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

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

输出格式

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

输入输出样例

  • 输入#1

    3 3
    1 19 2
    2 3 2
    1 0 1
    3
    1 3
    3 3
    2 2

    输出#1

    17

说明/提示

【样例解释】

起点为(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)

【数据规模】

对于百分百的数据

1N20001\le N\le 2000

1M2001\le M\le 200

1T2×1051\le T\le 2\times 10^5

笑死

0/50
首页