题目描述

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$ 所需的最小小时数。

3
3
1 -1 0
0 1 0
1 1 1
0 1 0
0 0 0
0 0 0
1 1 1
0 0 1
2
-1 -1
-1 -1
1 10
100 1000
1 0
0 1
3
-1 -1 -1
-1 -1 -1
0 0 0
1 1 3
5 1 4
0 0 0
0 0 0
0 0 0

Case #1: 0
Case #2: 1
Case #3: 2

提示

在样例 #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 完成