Problem Description

Given a $n \times m$ chessboard, all positions except one are covered by $1 \times 2$ dominoes, totaling $\frac{nm - 1}{2}$ dominoes.

Alice can make any number of moves, each move must ensure that the dominoes do not go out of the board and no two dominoes overlap.

There are several special positions on the board. If they are exposed, you lose, so you need to prevent Alice's moves from exposing these positions.

You can choose to fix any number of dominoes, fixing a domino requires a certain cost. As Bob, you want to use the least cost to ensure that no matter how Alice moves, those special positions will not be exposed. Find this minimum cost.

If no matter how you fix the dominoes, it cannot be satisfied, output "GG".

Input Format

The first line contains three integers $n, m, k(1 \leq n, m \leq 1001, 0 \leq k \leq n \times m)$, representing the size of the board and the number of special positions. It is guaranteed that both $n$ and $m$ are odd.

The next line contains $\frac{nm - 1}{2}$ numbers, the $i$-th number $a_i(1 \leq a_i \leq 10^9)$ represents the cost required to fix the $i$-th domino.

The next $k$ lines, each containing two integers $x, y(1 \leq x \leq n, 1 \leq y \leq m)$, indicate that $(x, y)$ is a special position. The $k$ special positions are not guaranteed to be distinct; if there are duplicates, the later one can be ignored.

The next $n$ lines, each containing $m$ numbers $v_{i, j}(0 \leq v_{i, j} \leq \frac{nm - 1}{2})$, represent the coverage of the board. If $v_{i,j} = 0$, it means the position is not covered; otherwise, it means the position is covered by the domino numbered $v_{i, j}$.

Output Format

One line containing an integer, representing the answer.

Sample Input and Output

Sample Input #1

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

Sample Output #1

GG

Sample Input #2

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

Sample Output #2

6

Sample Input #3

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

Sample Output #3

6

见题面 Input 部分

见题面 Output 部分