Prof. Pang 正在玩“管道大师”（Tube Master）。游戏场地被 $(n+1) \times m$ 条水平管道和 $n \times (m+1)$ 条垂直管道分割成 $n \times m$ 个单元格。已知 $nm$ 为偶数。管道共有 $(n+1)(m+1)$ 个交点。我们将坐标为 $(i, j)$ 的交点（$1 \le i \le n+1, 1 \le j \le m+1$）称为“交点 $(i, j)$”。我们将以交点 $(i, j), (i+1, j), (i, j+1), (i+1, j+1)$ 为顶点的单元格称为“单元格 $(i, j)$”（对于所有 $1 \le i \le n, 1 \le j \le m$）。此外，每个单元格 $(i, j)$ 包含一个整数 $count_{i,j}$。

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

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

1. 每个交点连接的管道数量必须为 0 或 2。
2. 对于每个单元格 $(i, j)$，其相邻的转折点数量必须恰好为 $count_{i,j}$。转折点是指连接了恰好 1 条水平管道和 1 条垂直管道的交点。如果交点 $(x, y)$ 是单元格 $(i, j)$ 的一个顶点，则称转折点 $(x, y)$ 与单元格 $(i, j)$ 相邻。

使用连接交点 $(i, j)$ 和 $(i, j+1)$ 的管道成本为 $a_{i,j}$。使用连接交点 $(i, j)$ 和 $(i+1, j)$ 的管道成本为 $b_{i,j}$。请帮助 Prof. Pang 找出他应该使用哪些管道，以满足上述限制并使总成本最小化。

输入格式

第一行包含一个正整数 $T$，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $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}$ ($1 \le a_{i,j} \le 10^9$)，由单个空格分隔。

接下来的 $n$ 行中，第 $i$ 行包含 $m+1$ 个整数 $b_{i,1}, b_{i,2}, \dots, b_{i,m+1}$ ($1 \le b_{i,j} \le 10^9$)，由单个空格分隔。

保证 $nm$ 为偶数，且所有测试用例中 $nm$ 的总和不超过 $10^4$。

输出格式

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

样例

输入 1

4
2 3
4 3 2
2 3 4
2 1 1
2 1 2
1 2 1
1 2 1 2
1 1 1 2
2 2
2 1
2 1
1 2
2 2
1 2
1 2 1
2 1 1
3 2
1 2
3 3
3 2
1 1
1 1
2 2
1 1
1 1 1
1 1 1
2 2 2
2 2
1 2
3 4
5 6
7 8
9 10
11 12 13
14 15 16

输出 1

13
8
11
-1