题目描述

一个 $n \times m$ 的棋盘，除了某一个位置，其它所有位置都被 $1 \times 2$ 的多米诺骨牌覆盖，所以一共有 $\frac{nm - 1}{2}$ 个多米诺骨牌。

Alice 可以进行任意多次移动，每次移动需要保证移动后多米诺骨牌不超出棋盘，且不能存在两个多米诺骨牌重叠。

棋盘上有若干个特殊位置，一旦它们露出来，你就输了，所以你要避免 Alice 的移动使这些位置露出来。

你可以选择固定任意多个多米诺骨牌，固定一个骨牌需要一定的代价，身为 Bob 的你希望用最少的代价，使得无论 Alice 怎么移动，那些特殊位置都不会露出来，求出这个最小代价。

如果无论怎么固定，都不能满足，输出 "GG"。

输入格式

第一行三个整数 $n, m, k(1 \leq n, m \leq 1001, 0 \leq k \leq n \times m)$，分别表示棋盘的大小以及特殊位置的个数。保证 $n$ 和 $m$ 都是奇数。

接下来一行 $\frac{nm - 1}{2}$ 个数，第 $i$ 个数 $a_i(1 \leq a_i \leq 10^9)$表示固定第 $i$ 个骨牌需要的代价。

接下来 $k$ 行，每行两个整数 $x, y(1 \leq x \leq n, 1 \leq y \leq m)$，表示$(x, y)$ 是一个特殊位置。不保证这 $k$ 个特殊位置互不相同，如果有相同的，忽略后一个即可。

接下来 $n$ 行，每行 $m$ 个数 $v_{i, j}(0 \leq v_{i, j} \leq \frac{nm - 1}{2})$，表示棋盘的覆盖情况。如果 $v_{i,j} = 0$，表示该位置未被覆盖，否则表示这个位置被编号为 $v_{i, j}$ 的骨牌覆盖。

输出格式

一行一个整数，表示答案。

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

GG

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

6

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

6