Description

In an $r \times c$ grid matrix, a courier starts from the company at $(1,1)$ and needs to deliver pizzas to $d$ cells. Before leaving, he has already taken all the pizzas with him, so he will not waste time going back and forth.

At any moment, the courier can only move left or right, but if he is in column $1$ or column $c$, he can move up or down. Each time he arrives at a cell, it costs the time assigned to that cell. (If he arrives multiple times, the cost is added multiple times.)

To be more efficient, he wants to know the minimum total time needed to finish deliveries to these $d$ delivery points.

Input Format

The first line contains two integers $r, c$, representing the number of rows and columns of the matrix.

The next $r$ lines each contain $c$ integers, where each integer is the time cost to step onto that cell.

The next line contains an integer $d$, representing the total number of delivery points that must be visited.

The next $d$ lines each contain two integers $a, b$, meaning the courier must deliver to the cell at row $a$ and column $b$.

Although the courier wants to minimize the time, he must deliver in the order given in the input, otherwise customers will be unhappy.

Output Format

Output one integer in one line, representing the minimum delivery time.

3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2

17

2 5
0 0 0 0 0
1 4 2 3 2
4
1 5
2 2
2 5
2 1

9

Hint

Explanation for Sample 1

The shortest delivery route is:

$(1,1),(2,1),(3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (2, 3), (3, 3), (2, 3),(2, 2)$.

The total time is: $1+2+1+0+1+2+2+2+1+2+3=17$.

Constraints

• For $70\%$ of the testdata, it is guaranteed that $r \le 250$.
• For $100\%$ of the testdata, it is guaranteed that $1 \le r \le 2000$, $1 \le c \le 200$, $1 \le d \le 2 \times 10^5$, $1 \le a \le r$, $1 \le b \le c$.

Notes

This problem is translated from COCI2008-2009 CONTEST #6 T5 DOSTAVA。

Translated by ChatGPT 5