Checksum

Grace and Edsger are constructing an $N \times N$ boolean matrix $A$. The element in the $i$-th row and $j$-th column is written $A_{i,j}$. They decide to note down the checksum (defined as the bitwise XOR of the given list of elements) along each row and each column. The checksum of the $i$-th row is written $R_i$, and the checksum of the $j$-th column is written $C_j$.

For example, if $N = 2$ and $A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$, then $R = \begin{bmatrix} 1 & 0 \end{bmatrix}$ and $C = \begin{bmatrix} 0 & 1 \end{bmatrix}$.

Once they finish the matrix, Edsger stores it on his computer. Due to a virus, some elements of matrix $A$ are replaced with $-1$ on Edsger's computer. Luckily, Edsger still remembers the checksum values. He wants to restore the matrix and asks Grace for help. After some investigation, it turns out that recovering the original value of $A_{i,j}$ from the disk takes Grace $B_{i,j}$ hours. Given the final matrix $A$, the cost matrix $B$, and the checksums along each row ($R$) and column ($C$), can you help Grace decide the minimum total number of hours needed to restore the original matrix $A$?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains a single integer $N$.

The next $N$ lines each contain $N$ integers representing the matrix $A$. The $j$-th element on the $i$-th line is $A_{i,j}$.

The next $N$ lines each contain $N$ integers representing the matrix $B$. The $j$-th element on the $i$-th line is $B_{i,j}$.

The next line contains $N$ integers representing the checksums of the rows. The $i$-th element is $R_i$.

The next line contains $N$ integers representing the checksums of the columns. The $j$-th element is $C_j$.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum number of hours to restore matrix $A$.

• $1 \le T \le 100$.
• $-1 \le A_{i,j} \le 1$, for all $i$, $j$.
• $1 \le B_{i,j} \le 1000$ for $i$, $j$ where $A_{i,j} = -1$, and $B_{i,j} = 0$ otherwise.
• $0 \le R_i \le 1$, for all $i$.
• $0 \le C_j \le 1$, for all $j$.
• There is at least one way to replace the $-1$ entries in $A$ with $0$ or $1$ so that $R$ and $C$ are satisfied.

In Sample Case #1, $A_{1,2}$ can be restored using the checksum of either the 1st row or the 2nd column. So Grace can restore the matrix without spending any time recovering data.

In Sample Case #2, Grace spends one hour to recover $A_{1,1}$. After that, she can use the checksums of the 1st row and the 1st column to restore $A_{1,2}$ and $A_{2,1}$ respectively. Then she can use the checksum of the 2nd row to restore $A_{2,2}$. So Grace can restore the matrix by spending one hour.

In Sample Case #3, Grace can spend one hour to recover $A_{1,1}$ and another hour to recover $A_{2,2}$. After that, she can use the checksums to restore the rest of the matrix. So Grace can restore the matrix by spending two hours in total.