P10820 [EC Final 2020] Tube Master III

庞教授正在玩「Tube Master」。 游戏场地被 $(n + 1) \times m$ 条水平管道和 $n \times (m + 1)$ 条垂直管道划分为 $n \times m$ 个单元格。乘积 $nm$ 是一个\textbf{偶数}。管道的交叉点共有 $(n + 1) (m + 1)$ 个。交叉点的二维坐标为 $(i, j)$，其中 $1\le i\le n+1$，$1\le j\le m+1$。我们将坐标为 $(i, j)$ 的交叉点称为交叉点 $(i, j)$。我们将以交叉点 $(i, j), (i+1, j), (i, j+1), (i+1, j+1)$ 为角的单元格称为单元格 $(i, j)$，其中 $1\le i\le n$，$1\le j\le m$。此外，每个单元格 $(i, j)$ 包含一个整数 ${count}_{i, j}$。  上图展示了一个 $n = 3, m = 2$ 的游戏场地（第三个样例）。 庞教授决定使用一些管道。然而，游戏有几个奇怪的限制条件。 - 每个交叉点要么连接 $0$ 根管道，要么连接 $2$ 根管道。 - 恰好有 ${count}_{i, j}$ 个转折点与单元格 $(i, j)$ 相邻。转折点是指恰好有 $1$ 根水平管道和 $1$ 根垂直管道连接到它的交叉点。转折点 $(x, y)$ 与单元格 $(i, j)$ 相邻是指交叉点 $(x, y)$ 是单元格 $(i, j)$ 的一个角。 使用连接交叉点 $(i, j)$ 和 $(i, j+1)$ 的管道的费用是 $a_{i, j}$。使用连接交叉点 $(i, j)$ 和 $(i+1, j)$ 的管道的费用是 $b_{i, j}$。请帮助庞教授找出他应该使用哪些管道，以便满足限制条件并使总费用最小。

第一行包含一个正整数 $T$，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n$ 和 $m$ ($1 \leq n, m \leq 100$)，用一个空格分隔。 接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 ${count}_{i, 1}, {count}_{i, 2}, \dots, {count}_{i, m}$ ($0 \leq {count}_{i, j} \leq 4$)，用空格分隔。 接下来的 $n+1$ 行中，第 $i$ 行包含 $m$ 个整数 ${a}_{i, 1}, {a}_{i, 2}, \dots, {a}_{i, m}$ ($1 \leq {a}_{i, j} \leq 10^9$)，用空格分隔。 接下来的 $n$ 行中，第 $i$ 行包含 $m+1$ 个整数 ${b}_{i, 1}, \mathit{b}_{i, 2}, \dots, {b}_{i, m+1}$ ($1 \leq {b}_{i, j} \leq 10^9$)，用空格分隔。 保证 $nm$ 是一个\textbf{偶数}，且所有测试用例中 $nm$ 的总和不超过 $10^4$。

对于每个测试用例，输出一个整数，表示最小费用。 如果没有有效的配置，输出 `-1`。

（由 ChatGPT 4o 翻译）