Matrix Transformation

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

Medium6GreedyMatrixSimulationNo attempts yetTime limit2sMemory limit128 MB

Description

Examples4

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.