P3159 [CQOI2012] Swap Pieces

There is a black-and-white board with $n$ rows and $m$ columns. Each time, you may swap the pieces in two adjacent cells (**adjacent means sharing an edge or a vertex**) to reach a target state. The cell at row $i$, column $j$ may participate in at most $m_{i,j}$ swaps.

The first line contains two integers $n, m$. The next $n$ lines describe the initial state; each line is a binary string of length $m$, where $0$ denotes a black piece and $1$ denotes a white piece. The next $n$ lines describe the target state in the same format as the initial state. The next $n$ lines each contain a string of $m$ digits from '0' to '9', representing the upper bound on the number of times each cell may participate in swaps.

Output a single line with the minimum total number of swaps. If there is no solution, output $-1$.

### Constraints For $100\%$ of the testdata, $1 \le n, m \le 20$. Translated by ChatGPT 5