Matrix Swaps

You are given two N×M matrices A and B consisting only of 0s and 1s, and a matrix C that limits how often each cell may be used. One swap operation chooses two cells of A that are adjacent horizontally, vertically, or diagonally, and exchanges their values. Cell (i, j) may be included in at most C_i,j swap operations during the whole process. Find the minimum number of swap operations needed to make matrix A equal to matrix B.

The first line contains N and M, the dimensions of the matrices. The next N lines describe matrix A, one row per line. The following N lines describe matrix B in the same format, and the final N lines describe matrix C in the same format. Each row is given as a length-M string without spaces.

Print the minimum number of swap operations needed to change matrix A into matrix B. If it is impossible, print -1.

• 1 ≤ N, M ≤ 20
• 0 ≤ A_i,j, B_i,j ≤ 1
• 0 ≤ C_i,j ≤ 9