Matrix Transformation

Time limit2sMemory limit128 MB

Summary

Given two binary matrices, find the minimum number of 3x3 submatrix bit-flips needed to turn matrix A into matrix B, or report impossibility.

Level: Medium6 of 10
Topics: Greedy, Matrix, Simulation
Solved: No attempts yet

Problem

You are given two matrices A and B consisting only of 0s and 1s. In one operation, choose any 3×3 submatrix and flip every element inside it: 0 becomes 1, and 1 becomes 0.

Find the minimum number of operations needed to make matrix A equal to matrix B.

Input

The first line contains the matrix dimensions N and M. Both N and M are natural numbers not greater than 50.

The next N lines contain matrix A, followed by N lines containing matrix B. Each row is a length-M string consisting only of 0s and 1s.

Output

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

Examples4

Example 1
Input
```
3 4
0000
0010
0000
1001
1011
1001
```
Expected output
```
2
```
Example 2
Input
```
3 3
111
111
111
000
000
000
```
Expected output
```
1
```
Example 3
Input
```
1 1
1
0
```
Expected output
```
-1
```

Example 4

Input

Expected output