체크섬

Grace와 Edsger는 $N \times N$ 불리언 행렬 $A$를 만들고 있다. $i$번째 행과 $j$번째 열의 원소는 $A_{i,j}$로 나타낸다. 두 사람은 각 행과 각 열의 체크섬(주어진 원소들의 bitwise XOR)을 기록하기로 한다. $i$번째 행의 체크섬은 $R_i$, $j$번째 열의 체크섬은 $C_j$로 나타낸다.

예를 들어 $N = 2$이고 $A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$이면 $R = \begin{bmatrix} 1 & 0 \end{bmatrix}$이고 $C = \begin{bmatrix} 0 & 1 \end{bmatrix}$이다.

행렬을 완성한 뒤 Edsger는 행렬을 자신의 컴퓨터에 저장한다. 그런데 바이러스 때문에 Edsger의 컴퓨터에서 행렬 $A$의 일부 원소가 $-1$로 바뀌었다. 다행히 Edsger는 체크섬 값은 아직 기억하고 있다. 그는 행렬을 복원하고 싶어 Grace에게 도움을 청한다. 조사 끝에, 디스크에서 $A_{i,j}$의 원래 값을 복구하는 데 Grace가 $B_{i,j}$시간을 쓴다는 사실을 알아냈다. 최종 행렬 $A$, 비용 행렬 $B$, 각 행의 체크섬 $R$과 각 열의 체크섬 $C$가 주어질 때, 원래 행렬 $A$를 복원하는 데 필요한 최소 총 시간을 Grace가 결정하도록 도와줄 수 있는가?

입력의 첫 줄에는 테스트 케이스의 수 $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 \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$를 만족시키는 방법이 적어도 하나 존재한다.

Sample Case #1에서 $A_{1,2}$는 1번째 행 또는 2번째 열의 체크섬을 이용해 복원할 수 있다. 따라서 Grace는 데이터를 복구하는 데 시간을 전혀 쓰지 않고 행렬을 복원할 수 있다.

Sample Case #2에서 Grace는 $A_{1,1}$을 복구하는 데 1시간을 쓴다. 그 뒤 1번째 행과 1번째 열의 체크섬을 각각 이용해 $A_{1,2}$와 $A_{2,1}$을 복원할 수 있다. 그리고 2번째 행의 체크섬을 이용해 $A_{2,2}$를 복원할 수 있다. 따라서 Grace는 1시간을 써서 행렬을 복원할 수 있다.

Sample Case #3에서 Grace는 $A_{1,1}$을 복구하는 데 1시간, $A_{2,2}$를 복구하는 데 1시간을 더 쓸 수 있다. 그 뒤 체크섬을 이용해 나머지 행렬을 복원할 수 있다. 따라서 Grace는 총 2시간을 써서 행렬을 복원할 수 있다.