COCI 2008/2009, Contest #6

Task DOSTAVA

Little Ivica recently got a job delivering pizzas for the most popular pizzeria in town.

At the start of his work day, he receives a list with the locations to which he needs to deliver pizzas, in order in which the locations are given.

The city is divided into R×C cells. The rows are numbered 1 through R, columns 1 through C. From every cell, it is possible to move to neighbouring cells to the left and right. Moving up or down is only allowed in the first and last columns (columns 1 and C).

The pizzeria is in the top left corner (1, 1) and this is the location Ivica starts from. Ivica takes with him all the pizzas he will deliver that day so he does not have to return to the pizzeria between deliveries or after the last delivery.

For each location in the city, Ivica knows how much time he will spend every time he is in it (trying to get through the intersection, for example).

Write a program that calculates the smallest amount of time for Ivica to deliver all the pizzas.

Input

The first line contains the integers R and C (1 ≤ R ≤ 2000, 1 ≤ C ≤ 200), the dimensions of the city. Each of the following R lines contains C integers. These are the times Ivica spends every time he enters a location. The times will be integers between 0 and 5000, inclusive.

The next line contains an integer D (1 ≤ D ≤ 200 000), the number of pizza deliveries that day. (No, it's not unrealistically large at all.)

Each of the following D lines contains two integers A and B (1 ≤ A ≤ R, 1 ≤ B ≤ C), the location to which a pizza must be delivered. The pizzas are given in the order in which they must be delivered. No location will be given twice in a row.

Output

Output the smallest amount of time for Ivica to deliver all the pizzas.

Scoring

In test cases worth 70% of points, R will be at most 250.

Examples

Input

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

Output

17

Input

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

Output

9

In the first example, the shortest path goes through the following locations:
(1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (2, 3), (3, 3), (2, 3) and (2, 2).
The locations in bold show where Mirko made deliveries.
The total time for the deliveries is 1+2+1+0+1+2+2+2+1+2+3=17.

All Submissions
Best Solutions


Point Value: 30 (partial)
Time Limit: 4.00s
Memory Limit: 128M
Added: Mar 10, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...