디지털 보드 복원

문제

0과 1로만 이루어진 N×M 크기의 디지털 보드가 있다. 현재 보드의 상태를 A, 목표 상태를 B라고 하자.

보드를 조작하는 유일한 방법은 어떤 3×3 크기의 부분 영역을 선택하여 그 안의 모든 값을 반전시키는 것이다 (0→1, 1→0). 단, 행렬의 범위를 벗어나는 3×3 영역은 선택할 수 없다. 따라서 3×3 영역의 왼쪽 위 모서리 칸은 1 ≤ 행 번호 ≤ N-2, 1 ≤ 열 번호 ≤ M-2 범위 내에 있어야 한다.

A를 B로 바꾸는 데 필요한 최소 조작 횟수를 구하라. 불가능한 경우 -1을 출력하라.

입력

첫째 줄에 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 50)

둘째 줄부터 N개의 줄에 보드 A의 상태가 주어진다. 각 줄은 0과 1로만 이루어진 길이 M의 문자열이다.

그 다음 N개의 줄에 보드 B의 상태가 주어진다. 각 줄은 0과 1로만 이루어진 길이 M의 문자열이다.

출력

첫째 줄에 A를 B로 바꾸는 데 필요한 최소 조작 횟수를 출력한다. 불가능한 경우 -1을 출력한다.

입출력 예시

입력 1

3 3
111
111
111
000
000
000

출력 1

1

입력 2

2 2
01
10
01
10

출력 2

0

입력 3

1 1
1
0

출력 3

-1

입력 4

5 5
00000
00000
00000
00000
00000
00111
11011
11011
11100
00000

출력 4

2