P4701 Sticky Dominoes

On an $n \times m$ board, all cells except one are covered by $1 \times 2$ dominoes, so there are $\frac{nm - 1}{2}$ dominoes in total. Alice may make arbitrarily many moves. After each move, all dominoes must remain within the board, and no two dominoes may overlap. There are several special cells on the board. Once any of them becomes exposed, you lose, so you must prevent Alice’s moves from exposing these cells. You may choose to fix any number of dominoes in place. Fixing one domino costs a certain amount. As Bob, you want to pay the minimum total cost so that no matter how Alice moves, those special cells will never be exposed. Find this minimum cost. If it is impossible no matter how you fix the dominoes, output "GG".

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 cells. It is guaranteed that $n$ and $m$ are both odd. The next line contains $\frac{nm - 1}{2}$ numbers. The $i$-th number $a_i(1 \leq a_i \leq 10^9)$ denotes the cost to fix the $i$-th domino. The next $k$ lines each contain two integers $x, y(1 \leq x \leq n, 1 \leq y \leq m)$, indicating that $(x, y)$ is a special cell. The $k$ special cells are not guaranteed to be distinct; if duplicates occur, ignore any later occurrence. The next $n$ lines each contain $m$ numbers $v_{i, j}(0 \leq v_{i, j} \leq \frac{nm - 1}{2})$, describing the coverage of the board. If $v_{i, j} = 0$, that cell is uncovered; otherwise, it is covered by the domino numbered $v_{i, j}$.

Output a single line with the answer: either a single integer representing the minimum total cost, or GG if it is impossible.

Translated by ChatGPT 5