Description

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.

Input Format

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 Format

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

3 3
110
000
001
000
110
100
222
222
222

4

Hint

Constraints

For $100\%$ of the testdata, $1 \le n, m \le 20$.

Translated by ChatGPT 5