[CQOI2012] 交换棋子

题目描述

有一个 $n$ 行 $m$ 列的黑白棋盘,你每次可以交换两个相邻格子(**相邻是指有公共边或公共顶点**)中的棋子,最终达到目标状态。要求第 $i$ 行第 $j$ 列的格子只能参与 $m_{i,j}$ 次交换。

输入输出格式

输入格式


第一行包含两个整数 $n,m$。以下 $n$ 行为初始状态,每行为一个包含 $m$ 个字符的 $01$ 串,其中 $0$ 表示黑色棋子,$1$ 表示白色棋子。以下 $n$ 行为目标状态,格式同初始状态。以下 $n$ 行每行为一个包含 $m$ 个 $0\sim9$ 数字的字符串,表示每个格子参与交换的次数上限。

输出格式


输出仅一行,为最小交换总次数。如果无解,输出 $-1$。

输入输出样例

输入样例 #1

3 3
110
000
001
000
110
100
222
222
222

输出样例 #1

4

说明

### 数据规模与约定 对于 $100\%$ 的数据,$1\leq n,m\leq20$。