Yuuka 正在玩“Tube Master”游戏。游戏场地被划分为 $n \times m$ 个单元格和 $(n+1) \times (m+1)$ 个交叉点，它们由 $(n+1) \times m$ 条水平管道和 $n \times (m+1)$ 条垂直管道连接。单元格标记为 $(i, j)$，其中 $1 \le i \le n, 1 \le j \le m$；交叉点标记为 $(i, j)$，其中 $1 \le i \le (n+1), 1 \le j \le (m+1)$。此外，每个单元格 $(i, j)$ 包含一个整数 $count_{i,j}$。

上图展示了一个 $n = m = 3$ 的游戏场地（第三个样例）。

Yuuka 决定使用其中的一些管道。然而，游戏有几个奇怪的限制：

1. 每个交叉点连接的管道使用数量要么为 0，要么为 2。
2. 不得同时使用两条连续的水平管道，也不得同时使用两条连续的垂直管道。如果两条管道共享同一个交叉点，则称它们是连续的。
3. 环绕单元格 $(i, j)$ 的管道数量必须恰好为 $count_{i,j}$。

连接交叉点 $(i, j)$ 和 $(i, j+1)$ 的管道费用为 $a_{i,j}$，连接交叉点 $(i, j)$ 和 $(i+1, j)$ 的管道费用为 $b_{i,j}$。Yuuka 希望找到一个满足上述限制的配置，使得总费用最小。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 100$)。 接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $count_{i,1}, count_{i,2}, \dots, count_{i,m}$ ($0 \le count_{i,j} \le 4$)。 接下来的 $(n+1)$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$。 最后 $n$ 行中，第 $i$ 行包含 $(m+1)$ 个整数 $b_{i,1}, b_{i,2}, \dots, b_{i,m+1}$。

数据范围：$1 \le a_{i,j}, b_{i,j} \le 10^9$。 保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^4$。

输出格式

对于每个测试用例，输出一个整数，表示配置的最小总费用。如果不存在合法的配置，则输出“-1”。

样例

输入 1

1 3
4 2 4
1 1 1
1 1 1
1 1 1 1
1 2
3 3
1 1
1 1
1 1 1
3 3
2 3 2
3 0 3
2 3 2
1 2 3
4 5 6
7 8 9
11 12 13
1 2 3 4
5 6 7 8
9 10 11 12

输出 1

8
-1
79