Parcel Delivery

A courier receives a list of locations to visit every day. All parcels must be delivered in exactly the order given in the list.

The city is divided into R*C cells. Rows are numbered from 1 to R from top to bottom, and columns are numbered from 1 to C from left to right.

From a cell, the courier may move one cell left or right. To move up or down, the courier must be in the first column or the last column; vertical movement is possible only along those two columns.

Delivery starts at the top-left cell (1, 1). The courier carries all parcels from the start, so there is no need to return to the starting point during or after the deliveries.

For each cell, the time needed to pass through that cell is given. The total time includes every cell actually visited, including the starting cell. Find the minimum time needed to deliver all parcels in order.

The first line contains the city size R and C. (1 <= R <= 2000, 1 <= C <= 200)

Each of the next R lines contains the time needed to pass through each cell. Every time value is an integer between 0 and 5000, inclusive.

The next line contains the number of parcels D. (1 <= D <= 200000)

Each of the next D lines contains the coordinates of the cell where the next parcel must be delivered, in delivery order. The same cell may appear more than once, but the same cell is never given on two consecutive lines.

Print the minimum time needed to deliver all parcels in order.

In the first visible test case, one possible 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.