Chessboard Swaps with Limited Moves

You are given an \(n\)-row \(m\)-column chessboard where each cell contains a piece (represented as either 0 or 1). You are also given a target configuration of the board. In one move, you can swap the pieces of two adjacent cells. Two cells are considered adjacent if they share a common edge or vertex (i.e. they are 8-connected neighbors).

There is an additional restriction: the cell in the \(i\)th row and \(j\)th column is allowed to participate in at most \(m_{i,j}\) swaps. A cell participates in a swap if its piece is moved (i.e. if it is one of the two cells chosen in a swap, its counter increases by one).

Your task is to determine the minimum number of swaps needed to convert the initial configuration into the target configuration without exceeding the allowed number of swaps on any cell. If it is impossible to achieve the target configuration under these constraints, output \(-1\).

Note: The input guarantees that the total number of pieces of each type (0 or 1) in the initial configuration equals that in the target configuration.

inputFormat

The first line contains two integers \(n\) and \(m\) (\(1 \leq n, m \leq 10\)), representing the number of rows and columns of the board.

The next \(n\) lines each contain \(m\) integers. The \(j\)th integer in the \(i\)th line is \(m_{i,j}\) (\(0 \leq m_{i,j} \leq 10\)), which is the maximum number of swaps allowed for the cell at row \(i\), column \(j\).

The following \(n\) lines each contain a string of length \(m\) consisting of characters '0' and '1', representing the initial configuration of the board.

The next \(n\) lines each contain a string of length \(m\) (again consisting of '0' and '1'), representing the target configuration of the board.

outputFormat

Output a single integer indicating the minimum number of swaps required to convert the initial configuration into the target configuration under the given constraints. If it is impossible, output \(-1\).

sample

2 2
1 1
1 1
01
10
10
01

2