Tube Master II

Yuuka is playing "Tube Master". The game field is divided into $n \times m$ cells and $(n + 1) \times (m + 1)$ crossings. The crossings are connected by $(n + 1) \times m$ horizontal tubes and $n \times (m + 1)$ vertical tubes. The cells are labeled $(i, j)$ for $1 \leq i \leq n$, $1 \leq j \leq m$, and the crossings are labeled $(i, j)$ for $1 \leq i \leq (n+1)$, $1 \leq j \leq (m+1)$. Each cell $(i, j)$ contains an integer $\mathit{count}\_{i, j}$.

Yuuka decides to use some of the tubes, subject to these restrictions:

1. Either 0 or 2 tubes connected to each crossing are used.
2. No two consecutive horizontal tubes are used at the same time, and no two consecutive vertical tubes are used at the same time. Two tubes are consecutive if and only if they share a crossing.
3. Exactly $\mathit{count}\_{i, j}$ of the tubes surrounding cell $(i, j)$ are used.

Using the tube connecting crossings $(i, j)$ and $(i, j + 1)$ costs $a\_{i, j}$. Using the tube connecting crossings $(i, j)$ and $(i + 1, j)$ costs $b\_{i, j}$. Find a configuration that satisfies the restrictions with the minimum total cost.

The input contains zero or more test cases and ends at end-of-file. For each test case:

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 100$).

The $i$-th of the following $n$ lines contains $m$ integers $\mathit{count}\_{i, 1}, \mathit{count}\_{i, 2}, \dots, \mathit{count}\_{i, m}$ ($0 \leq \mathit{count}\_{i, j} \leq 4$).

The $i$-th of the next $(n + 1)$ lines contains $m$ integers $a\_{i, 1}, a\_{i, 2}, \dots, a\_{i, m}$.

The $i$-th of the last $n$ lines contains $(m + 1)$ integers $b\_{i, 1}, b\_{i, 2}, \dots, b\_{i, m + 1}$.

The constraints are $1 \leq a\_{i, j}, b\_{i, j} \leq 10^9$. The sum of $n \cdot m$ over all test cases does not exceed $10^4$.

For each test case, output the minimum cost of a valid configuration. If no valid configuration exists, output "-1" instead.