체크섬

그레이스와 에츠허는 $\mathbf{N} \times \mathbf{N}$ 불리언 행렬 $\mathbf{A}$을 만들고 있다. $i$번째 행과 $j$번째 열의 원소는 $\mathbf{A_{i,j}}$로 나타낸다. 두 사람은 각 행과 열을 따라 체크섬(주어진 원소 목록의 비트 단위 XOR로 정의됨)을 기록하기로 한다. $i$번째 행의 체크섬은 $\mathbf{R_i}$로 나타낸다. $j$번째 열의 체크섬은 $\mathbf{C_j}$로 나타낸다.

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

행렬을 완성한 뒤 에츠허는 행렬을 자신의 컴퓨터에 저장한다. 하지만 바이러스 때문에 에츠허의 컴퓨터에 있는 행렬 $\mathbf{A}$의 일부 원소가 $-1$로 바뀌었다. 다행히도 에츠허는 체크섬 값을 여전히 기억하고 있다. 그는 행렬을 복원하고 싶어 그레이스에게 도움을 요청한다. 조사해 본 결과, 그레이스가 디스크에서 $\mathbf{A_{i,j}}$의 원래 값을 복구하는 데 $\mathbf{B_{i,j}}$시간이 걸린다. 최종 행렬 $\mathbf{A}$, 비용 행렬 $\mathbf{B}$, 각 행의 체크섬($\mathbf{R}$)과 각 열의 체크섬($\mathbf{C}$)이 주어질 때, 원래 행렬 $\mathbf{A}$을 복원하는 데 필요한 총 시간의 최솟값을 그레이스가 결정하도록 도와줄 수 있는가?

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. 모든 $i,j$에 대해 $-1 \le \mathbf{A_{i,j}} \le 1$. $\mathbf{A_{i,j}} = -1$인 $i,j$에 대해 $1 \le \mathbf{B_{i,j}} \le 1000$이고, 그 외에는 $\mathbf{B_{i,j}} = 0$. 모든 $i$에 대해 $0 \le \mathbf{R_i} \le 1$. 모든 $j$에 대해 $0 \le \mathbf{C_j} \le 1$. $\mathbf{R}$과 $\mathbf{C}$이 충족되도록 $\mathbf{A}$의 $-1$을 $0$ 또는 $1$로 바꾸는 방법이 적어도 하나 존재함이 보장된다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 4$.

테스트 세트 2

시간 제한: 35초. $1 \le \mathbf{N} \le 40$.

테스트 세트 3

시간 제한: 35초. $1 \le \mathbf{N} \le 500$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 정수 $\mathbf{N}$ 하나가 주어진다.

다음 $\mathbf{N}$개의 각 줄에는 행렬 $\mathbf{A}$을 나타내는 $\mathbf{N}$개의 정수가 주어진다. $i$번째 줄의 $j$번째 원소는 $\mathbf{A_{i,j}}$를 나타낸다.

다음 $\mathbf{N}$개의 각 줄에는 행렬 $\mathbf{B}$을 나타내는 $\mathbf{N}$개의 정수가 주어진다. $i$번째 줄의 $j$번째 원소는 $\mathbf{B_{i,j}}$를 나타낸다.

다음 줄에는 행의 체크섬을 나타내는 $\mathbf{N}$개의 정수가 주어진다. $i$번째 원소는 $\mathbf{R_i}$를 나타낸다.

다음 줄에는 열의 체크섬을 나타내는 $\mathbf{N}$개의 정수가 주어진다. $j$번째 원소는 $\mathbf{C_j}$을 나타낸다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$은 테스트 케이스 번호이며(1부터 시작한다), $y$는 행렬 $\mathbf{A}$을 복원하는 데 필요한 최소 시간이다.

예제 케이스 #1에서 $\mathbf{A_{1,2}}$은 1번째 행 또는 2번째 열의 체크섬 중 어느 하나를 사용해 복원할 수 있다. 따라서 그레이스는 데이터를 복구하는 데 시간을 전혀 쓰지 않고 행렬을 복원할 수 있다.

예제 케이스 #2에서 그레이스는 $\mathbf{A_{1,1}}$을 복구하는 데 한 시간을 쓴다. 그 후 1번째 행과 1번째 열의 체크섬을 사용해 각각 $\mathbf{A_{1,2}}$와 $\mathbf{A_{2,1}}$을 복원할 수 있다. 그런 다음 2번째 행의 체크섬을 사용해 $\mathbf{A_{2,2}}$을 복원할 수 있다. 따라서 그레이스는 한 시간을 써서 행렬을 복원할 수 있다.

예제 케이스 #3에서 그레이스는 $\mathbf{A_{1,1}}$을 복구하는 데 한 시간을 쓰고, $\mathbf{A_{2,2}}$을 복구하는 데 한 시간을 더 쓸 수 있다. 그 후 체크섬을 사용해 행렬의 나머지 부분을 복원할 수 있다. 따라서 그레이스는 총 두 시간을 써서 행렬을 복원할 수 있다.