题目背景

城市科技馆正在布置一面由黑白灯片组成的互动展示墙。工程师林澈负责控制程序，志愿者小悠负责检查机械滑轨。

展览开始前，灯墙当前显示的图案与设计稿并不一致。机械臂可以交换两个相邻位置的灯片；为了提高调整效率，横向、纵向以及斜向相邻的灯片都可以直接交换。

不过，每个位置下方的滑轨都有独立的耐久度限制。某个位置参与交换的次数过多，滑轨就可能在展览期间发生故障。林澈需要在不超过各位置耐久上限的前提下，将当前图案调整成设计稿，并让总交换次数尽可能少。

题目描述

给定三个大小均为 $n\times m$ 的矩阵：

• 初始矩阵 $A$；
• 目标矩阵 $B$；
• 使用次数上限矩阵 $C$。

矩阵 $A$ 和 $B$ 中的每个元素都是 0 或 1。

一次操作可以选择矩阵 $A$ 中两个相邻的格子，并交换它们的值。两个格子只要满足横向相邻、纵向相邻或斜向相邻，就视为相邻。换言之，若两个格子的行号之差和列号之差均不超过 $1$，且它们不是同一个格子，则可以交换。

每当一个格子作为交换操作的两个端点之一时，该格子的使用次数增加 $1$。

矩阵 $C$ 中的字符 $C_{i,j}$ 是一个十进制数字，表示格子 $(i,j)$ 在整个调整过程中最多可以参与多少次交换。

请在满足所有格子使用次数限制的前提下，将 $A$ 变为 $B$，并求最少需要多少次交换。

若无法完成，输出 -1。

输入格式

第一行输入两个整数 $n,m$，分别表示矩阵的行数和列数。

接下来 $n$ 行，每行输入一个长度为 $m$ 的 01 字符串，描述初始矩阵 $A$。

接下来 $n$ 行，每行输入一个长度为 $m$ 的 01 字符串，描述目标矩阵 $B$。

接下来 $n$ 行，每行输入一个长度为 $m$ 的数字字符串，描述使用次数上限矩阵 $C$。其中每个字符均为 0 到 9 之间的数字。

输出格式

输出一个整数，表示将矩阵 $A$ 变为矩阵 $B$ 所需的最少交换次数。

若不存在满足全部使用次数限制的方案，输出 -1。

样例 1

输入

3 3
110
000
001
000
110
100
222
222
222

输出

4

说明

一种最优方案依次交换下列位置：

1. $(1,1)$ 与 $(2,2)$；
2. $(1,2)$ 与 $(2,1)$；
3. $(3,3)$ 与 $(3,2)$；
4. $(3,2)$ 与 $(3,1)$。

这里的行、列编号均从 $1$ 开始。

样例 2

输入

1 2
10
01
11

输出

1

说明

直接交换两个格子即可。

样例 3

输入

3 3
111
000
111
111
000
111
013
537
136

输出

0

说明

初始矩阵已经与目标矩阵相同，不需要交换。

样例 4

输入

2 3
001
110
000
111
000
111

输出

-1

说明

第一行所有格子的使用次数上限均为 $0$，其中的 1 无法被移动到目标位置。

样例 5

输入

2 3
100
000
000
000
999
999

输出

-1

说明

交换操作不会改变矩阵中 1 的总数，而两个矩阵中 1 的数量不同。

数据范围

• $1\le n,m\le 20$；
• $A$ 和 $B$ 中的每个字符均为 0 或 1；
• $C$ 中的每个字符均为 0 到 9 之间的数字。