Pile of Cubes

The figure above shows a pile of cubes seen from an angle. The first floor holds 8 cubes, the second floor holds 4, and the third floor holds 1. Looking at this pile from the top, from the front, and from the right side gives the three pictures below, called the top view, the front view, and the right side view. None of the three views rotates the pile.

Read the other way around, three such pictures let you guess the pile they came from. Many different piles look the same from the top, the front, and the right side.

Write a program that computes the largest number of cubes a pile can use while still looking exactly like the three given views.

Some triples of pictures come from no pile at all. Gravity applies here as it does on Earth, so every cube rests on the ground or on another cube. Your program also has to decide whether the three pictures are possible in the first place.

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

The first line of each test case contains the picture size $N$ ($1 \le N \le 300$), and all three pictures are $N \times N$. The next $3N$ lines hold the top view, the front view, and the right side view in that order. Each picture is an $N \times N$ matrix of 0s and 1s, one matrix row per line, with entries separated by a single space. A 0 means no cube is seen at that position and a 1 means a cube is seen.

The matrices line up with the pile as follows. Split the ground into $N \times N$ cells, number the rows $1$ to $N$ from the back to the front, number the columns $1$ to $N$ from the left to the right, and let $h(r, c)$ be the number of cubes stacked on cell $(r, c)$.

• Row $r$, column $c$ of the top view is 1 exactly when $h(r, c) > 0$.
• In the front view the upper rows are the higher floors, so row $k$ stands for floor $N + 1 - k$, and column $c$ stands for the $c$-th ground column from the left. Row $k$, column $c$ is 1 exactly when some cell of that ground column carries at least $N + 1 - k$ cubes.
• In the right side view the upper rows are the higher floors as well. Column $m$ from the left stands for the ground row that is $m$-th from the front, which is row $N + 1 - m$. Row $k$, column $m$ is 1 exactly when some cell of that ground row carries at least $N + 1 - k$ cubes.

For each test case print one line. Print the largest number of cubes used by a pile that looks exactly like the three given views, or $-1$ when no pile looks like them. The empty pile counts as a pile, so three all-zero pictures give $0$.