Tube Master: Minimal Tube Selection

Professor Pang is playing Tube Master. The game field is divided into \(n \times m\) cells by \((n+1) \times m\) horizontal tubes and \(n \times (m+1)\) vertical tubes. Note that \(n \times m\) is an even number. There are \((n+1)\times(m+1)\) crossings of the tubes. The 2D coordinate of each crossing is \((i, j)\) for \(1 \le i \le n+1\) and \(1 \le j \le m+1\), and we refer to the crossing by its coordinates. Similarly, the cell whose four corners are crossings \((i,j)\), \((i+1,j)\), \((i,j+1)\), and \((i+1,j+1)\) is denoted as cell \((i,j)\) for \(1 \le i \le n\) and \(1 \le j \le m\). Each cell \((i,j)\) has an associated integer \(\text{count}_{i,j}\).

Professor Pang will choose some of the tubes with the following restrictions:

• At each crossing, either 0 or 2 tubes incident to it are used.
• A turning point is defined as a crossing where exactly one horizontal tube and exactly one vertical tube are used. For every cell \((i,j)\), exactly \(\text{count}_{i,j}\) of its four adjacent crossings (its corners) must be turning points.

Using a tube has a cost. It costs \(a_{i,j}\) to use the horizontal tube connecting crossings \((i,j)\) and \((i,j+1)\) (for \(1 \le i \le n+1,\ 1 \le j \le m\)), and it costs \(b_{i,j}\) to use the vertical tube connecting crossings \((i,j)\) and \((i+1,j)\) (for \(1 \le i \le n,\ 1 \le j \le m+1\)).

Your task is to help Prof. Pang choose a set of tubes that satisfies the above restrictions and minimizes the total cost. If no valid configuration exists, output -1.

Note: For this problem, all cells will have \(\text{count}_{i,j} = 0\) in the input test cases, so the optimal solution is to choose no tubes, incurring zero cost.

inputFormat

The input begins with two space-separated integers \(n\) and \(m\) \( (1 \le n, m \le 50,\ n\times m \mbox{ is even}) \).

Then follow \(n\) lines, each containing \(m\) integers. The \(j\)th integer in the \(i\)th line is \(\text{count}_{i,j}\) (in this problem, it will always be 0).

Then follow \(n+1\) lines, each containing \(m\) integers. The \(j\)th integer in the \(i\)th line is \(a_{i,j}\), the cost of using the horizontal tube connecting crossings \((i,j)\) and \((i,j+1)\).

Finally, there are \(n\) lines, each containing \(m+1\) integers. The \(j\)th integer in the \(i\)th line is \(b_{i,j}\), the cost of using the vertical tube connecting crossings \((i,j)\) and \((i+1,j)\).

outputFormat

Output a single integer: the minimum total cost to select the tubes satisfying the restrictions. If it is impossible to satisfy the restrictions, output -1.

Note: In the test cases provided for this problem, since all \(\text{count}_{i,j}\) values are 0, the correct output is always 0 (by selecting no tubes).

sample

1 2
0 0
1 2
3 4
5 6 7

0