Under construction

Still being built. Things may change

Matrix Swaps

Time limit2sMemory limit128 MB

Summary
Given binary matrices A and B and a per-cell swap-count limit matrix C, find the minimum number of adjacent (including diagonal) cell swaps to turn A into B, or report impossibility.
Level

Hard9 of 10

Topics
Graph, Shortest path, Matrix, Combinatorics
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

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

Examples7

  1. Example 1

    Input
    3 3
110
000
001
000
110
100
222
222
222
    Expected output
    4

  2. Example 2

    Input
    1 2
10
01
11
    Expected output
    1

  3. Example 3

    Input
    3 3
111
000
111
111
000
111
013
537
136
    Expected output
    0

  4. Example 4

    Input
    2 3
001
110
000
111
000
111
    Expected output
    -1

  5. Example 5

    Input
    2 3
100
000
000
000
999
999
    Expected output
    -1

  6. Example 6

    Input
    5 6
011101
110000
000011
000000
100000
110100
000011
000000
110001
000010
305713
537211
352421
242212
333313
    Expected output
    10

  7. Example 7

    Input
    2 2
10
00
00
01
11
11
    Expected output
    1