Number Link 是一款在 iOS 和 Android 等平台上广受欢迎的游戏。给定一个 $n$ 行 $m$ 列的棋盘，游戏的目标是将棋盘中数字相同的格子两两连接。一旦两个数字被配对，连接它们的路径将占据相应的格子。路径只能沿垂直或水平方向移动。注意，任何两条路径都不能在任何格子处相交（即不能共享同一个格子）。在本题中，你将游玩一个名为 Number Link ++ 的修改版本。示例如下图所示。

在这个新游戏中，你可以使用两种类型的路径。I 型路径用于连接两个奇偶性不同的数字格子（即连接一个奇数和一个偶数）。仅使用 I 型路径可能难以覆盖整个棋盘，因此我们允许使用 II 型路径，这是一种仅覆盖空格子的环形路径（II 型路径的唯一特殊情况是仅连接两个相邻空格子的路径；见上图）。天下没有免费的午餐，路径也不例外。当从格子 $(a, b)$ 移动到相邻格子 $(c, d)$ 时，你需要支付一定的通行费。从 $(c, d)$ 返回 $(a, b)$ 时费用相同。通常，一条路径的费用是该路径上所经过的所有格子之间的通行费之和。唯一的例外是 II 型路径的特殊情况，在这种情况下，你需要支付双倍费用（因为它是一个环）。整个游戏的总费用是所有路径费用之和。你能帮我找出一种路径方案，使得每个格子恰好位于一条路径上吗？如果存在这样的解，最小可能的总费用是多少？

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 50$)。接下来的 $n$ 行描述棋盘。每行包含 $m$ 个非负整数，描述从左到右每一列的状态。如果数字为零，则该格子为空；否则，它表示对应格子上的数字。接下来的 $n-1$ 行，每行包含 $m$ 个非负整数，描述垂直连接的费用。第 $i$ 行的第 $j$ 个数字是从格子 $(i, j)$ 移动到 $(i+1, j)$ 的费用。接下来的 $n$ 行，每行包含 $m-1$ 个非负整数，描述水平连接的费用。第 $i$ 行的第 $j$ 个数字是从格子 $(i, j)$ 移动到 $(i, j+1)$ 的费用。所有数字（包括答案）均可用 32 位有符号整数表示。

输出格式

对于每个测试用例，首先输出用例编号，然后输出一个整数，表示完成游戏的最小可能费用。如果不存在可行解，则输出 -1。

样例

样例输入 1

3
3 3
1 0 0
1 0 0
2 0 2
1 2 1
2 1 1
3 1
5 6
1 4
1 4
1 1 2 2
1 2 3
3 5
0 0 0 0 0
0 5 0 6 0
0 0 0 0 0
1 1000 1000 1000 1
1 1000 1000 1000 1
1 1 1 1
1000 1 1 1000
1 1 1 1

样例输出 1

Case #1: 10
Case #2: -1
Case #3: 14

说明

下图展示了分别对应样例 1 和样例 3 的解。在样例 1 中，你需要为红色路径支付双倍费用，因为它属于 II 型路径的特殊情况。