행렬 교환

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