행렬 교환

시간 제한2초메모리 제한128 MB

요약

0과 1로 이루어진 행렬 A를 행렬 B로 바꾸는 데 필요한 최소 인접(대각선 포함) 교환 횟수를 셀별 사용 한도 행렬 C 아래에서 구하는 문제입니다.

난이도: 어려움10점 중 9점
유형: 그래프, 최단 경로, 행렬, 조합론
정답자: 아직 제출이 없습니다

문제

0과 1로만 이루어진 N×M 행렬 A, B와 각 칸의 사용 가능 횟수 C가 주어진다. 한 번의 교환 연산은 행렬 A에서 가로, 세로 또는 대각선으로 인접한 두 칸을 골라 두 값을 서로 바꾸는 것이다. 칸 (i, j)는 전체 과정에서 최대 C_i,j번까지만 교환 연산에 포함될 수 있다. 행렬 A를 행렬 B와 같게 만들기 위해 필요한 교환 연산의 최소 횟수를 구한다.

입력

첫째 줄에 행렬의 크기 N과 M이 주어진다. 다음 N개의 줄에는 행렬 A가 한 줄에 한 행씩 주어진다. 이어서 N개의 줄에는 행렬 B가 같은 형식으로 주어지고, 마지막 N개의 줄에는 행렬 C가 같은 형식으로 주어진다. 각 행은 공백 없이 길이 M의 문자열로 주어진다.

출력

행렬 A를 행렬 B로 만들기 위한 교환 연산의 최소 횟수를 출력한다. 만들 수 없다면 -1을 출력한다.

제한

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

예제7

예제 1

입력

예상 출력

예제 2
입력
```
1 2
10
01
11
```
예상 출력
```
1
```

예제 3

입력

예상 출력

예제 4
입력
```
2 3
001
110
000
111
000
111
```
예상 출력
```
-1
```
예제 5
입력
```
2 3
100
000
000
000
999
999
```
예상 출력
```
-1
```

예제 6

입력

예상 출력

예제 7
입력
```
2 2
10
00
00
01
11
11
```
예상 출력
```
1
```