Efficient Pizza Delivery

In an \(r \times c\) grid, a courier starts at the company located at \((1,1)\) and must deliver pizzas to \(d\) designated cells. The grid is indexed from \(1\) to \(r\) in rows and \(1\) to \(c\) in columns. Each cell has an associated time cost. Every time the courier enters a cell, the cost of that cell is added to his total time (even if the cell is visited multiple times).

The courier can always move left or right. However, he is only allowed to move vertically (up or down) if he is currently in the first column (column 1) or the last column (column \(c\)). Note that if \(c = 1\) then vertical moves are always allowed because the only column is both first and last.

The courier is carrying all pizzas from the start so he can choose the order in which he visits the \(d\) delivery points. Determine the minimum total time required to visit all \(d\) delivery cells starting from \((1,1)\). The starting cell does not contribute to the cost initially, but if it is re‐visited later, its cost is added again.

Input Format: The input begins with three integers \(r\), \(c\) and \(d\). Then follow \(r\) lines each containing \(c\) integers where the \(j\)th integer of the \(i\)th line represents the time cost of cell \((i, j)\). Finally, there are \(d\) lines, each containing two integers representing the row and column of a delivery destination.

Movement rules:

• If the current cell is in a non-boundary column (i.e. not column 1 or column \(c\)), the courier can only move left or right (if within bounds).
• If the current cell is in column 1 or column \(c\), the courier can also move vertically (up or down) provided the destination cell is within bounds.

inputFormat

The first line contains three integers \(r\), \(c\), and \(d\) -- the number of rows, the number of columns and the number of delivery points respectively.

This is followed by \(r\) lines, each containing \(c\) space-separated integers where the \(j\)th integer in the \(i\)th line represents the time cost at cell \((i, j)\).

Finally, there are \(d\) lines, each with two integers representing the row and column of a delivery destination.

outputFormat

Output a single integer which is the minimum total time required to visit all \(d\) delivery points starting from \((1,1)\).

sample

3 3 2
1 2 3
4 5 6
7 8 9
3 3
1 3

20