Domino Fixation

You are given an \(n \times m\) board. All cells except one are covered by \(1\times 2\) dominoes; therefore, the number of dominoes is \(\frac{nm-1}{2}\). There is exactly one blank cell. Dominoes are placed in such a way that every domino covers two adjacent cells. Some cells on the board are special. If any special cell becomes uncovered after a move, you lose.

Alice can move unfixed dominoes arbitrarily many times. In one move a domino slides such that it remains completely inside the board and no two dominoes overlap. The move is performed by sliding a domino into the blank cell, hence the domino vacates one cell and covers the blank while leaving its other cell uncovered.

You, as Bob, can "fix" (i.e. lock) any subset of the dominoes at a cost (each domino has its own cost). A fixed domino cannot be moved. Your goal is to choose some dominoes to fix so that no matter how Alice moves the unfixed dominoes, none of the special cells will ever be uncovered. Determine the minimum total cost needed. If it is impossible to guarantee that the special cells never get exposed, output GG.

Note: A special cell must remain covered by its domino. If a special cell is initially the blank cell, then it is already uncovered and the answer is GG.

inputFormat

The input is given as follows:

 n m
 board_row_1
 board_row_2
 ...
 board_row_n
 k
 r1 c1
 r2 c2
 ...
 rk ck
 cost1 cost2 ... costX

Here, \(n\) and \(m\) are the dimensions of the board. The next \(n\) lines each contain \(m\) integers. Each integer represents the domino ID that covers that cell, or 0 if the cell is blank. It is guaranteed that all nonzero numbers appear exactly twice. \(k\) is the number of special cells. Each of the following \(k\) lines contains two integers \(r\) and \(c\) (1-indexed) that denote the special cell positions. Finally, there is a line with \(X = \frac{nm-1}{2}\) integers, where the i-th integer is the cost of fixing domino with ID i.

outputFormat

Output a single line containing the minimum total cost needed to secure all special cells so that they can never be exposed, or output GG if it is impossible.

sample

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

14