P16840 [GKS 2021 #A] Checksum

Grace 和 Edsger 正在构造一个 $N \times N$ 的布尔矩阵 $A$。第 $i$ 行第 $j$ 列的元素记为 $A_{i,j}$。他们决定记下每一行和每一列的校验和（定义为给定元素列表的按位异或）。第 $i$ 行的校验和记为 $R_i$，第 $j$ 列的校验和记为 $C_j$。 例如，若 $N = 2$，$A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$，则 $R = [1 \quad 0]$，$C = [0 \quad 1]$。 完成矩阵后，Edsger 将矩阵存储在电脑中。然而，由于病毒，Edsger 电脑中矩阵 $A$ 的某些元素被替换成了 $-1$。幸运的是，Edsger 仍然记得校验和的值。他想恢复矩阵，并向 Grace 寻求帮助。经过调查，Grace 从磁盘恢复 $A_{i,j}$ 的原始值需要花费 $B_{i,j}$ 小时。给定最终的矩阵 $A$、代价矩阵 $B$ 以及每一行和每一列的校验和（$R$ 和 $C$），你能帮助 Grace 确定恢复原始矩阵 $A$ 所需的最小总小时数吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。 每个测试用例的第一行包含一个整数 $N$。 接下来的 $N$ 行，每行包含 $N$ 个整数，表示矩阵 $A$。第 $i$ 行的第 $j$ 个元素表示 $A_{i,j}$。 再接下来的 $N$ 行，每行包含 $N$ 个整数，表示矩阵 $B$。第 $i$ 行的第 $j$ 个元素表示 $B_{i,j}$。 下一行包含 $N$ 个整数，表示行的校验和。第 $i$ 个元素表示 $R_i$。 再下一行包含 $N$ 个整数，表示列的校验和。第 $j$ 个元素表示 $C_j$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是恢复矩阵 $A$ 所需的最小小时数。

在样例 #1 中，$A_{1,2}$ 可以通过第 $1$ 行的校验和或第 $2$ 列的校验和恢复。因此，Grace 无需花费任何时间恢复数据即可恢复矩阵。 在样例 #2 中，Grace 花费 $1$ 小时恢复 $A_{1,1}$。之后，她可以利用第 $1$ 行的校验和恢复 $A_{1,2}$，利用第 $1$ 列的校验和恢复 $A_{2,1}$，然后利用第 $2$ 行的校验和恢复 $A_{2,2}$。因此，Grace 只需花费 $1$ 小时即可恢复矩阵。 在样例 #3 中，Grace 可以花费 $1$ 小时恢复 $A_{1,1}$，再花费 $1$ 小时恢复 $A_{2,2}$。之后，她可以利用校验和恢复矩阵的其余部分。因此，Grace 总共花费 $2$ 小时即可恢复矩阵。 ### 限制条件 $1 \le T \le 100$。 对于所有 $i, j$，$-1 \le A_{i,j} \le 1$。 对于 $A_{i,j} = -1$ 的 $(i, j)$，$1 \le B_{i,j} \le 1000$，否则 $B_{i,j} = 0$。 对于所有 $i$，$0 \le R_i \le 1$。 对于所有 $j$，$0 \le C_j \le 1$。 保证至少存在一种将 $A$ 中的 $-1$ 替换为 $0$ 或 $1$ 的方式，使得 $R$ 和 $C$ 成立。 **测试集 1** $1 \le N \le 4$。 **测试集 2** $1 \le N \le 40$。 **测试集 3** $1 \le N \le 500$。 翻译由 DeepSeek V4 Pro 完成