城市中有$$$n \times m$$$个十字路口,名为十字路口$$$(1, 1), (1, 2),\ldots, (n, m)$$$。第一个数字代表行,第二个数字代表列。
存在且只存在 $$$(i,j)$$$ 和 $$$(i+1,j)$$$ 之间或 $$$(i,j)$$$ 和 $$$(i,j+1)$$$ 之间的街道。 $$$(i, j)$$$ 和 $$$(i + 1, j)$$$ 之间的街道权重为 $$$w_{i,j}$$$,$$$(i, j)$$$ 和 $$$(i, j + 1)$$$ 之间的街道权重为 $$$v_{i,j}$$$。
西蒙斯希望重建一些街道。由于一些事故,一些街道 不能 被重建,而其他则可选被重建。
对于每个十字路口,如果与其相邻的重建街道数量为 甚至,西蒙斯称十字路口 优雅。如果所有的十字路口都是 优雅,西蒙斯呼吁重建 不错 重建的.
的 美女 计算如下:
- 首先, 美女 是 $$$0$$$。
- 对于每个 行 $$$i$$$从$$$1$$$到$$$n - 1$$$,令重建的街道柱为$$$c_1 \lt c_2 \lt c_3 \lt \cdots$$$,添加$$$w_{i, c_1} - w_{i, c_2} + w_{i, c_3} - w_{i, c_4}+\cdots$$$ 到 美女.
- 同样,对于每个 栏目 $$$j$$$从$$$1$$$到$$$m - 1$$$,令重建的街道行数为$$$r_1 \lt r_2 \lt r_3 \lt \cdots$$$,添加$$$v_{r_1, j} - v_{r_2, j} + v_{r_3, j} - v_{r_4, j}+\cdots$$$ 到 美女.
换句话说,如果一条街道是在其行或列中重建的奇数索引街道,则将其权重添加到 美女;否则从 美女.
例如,考虑下面的街道和十字路口,没有任何无法重建的街道:
我们可以有一个 不错 重建的 重构如下: 重建的
的 美女 是$$$3+4+2-(-9)-(-2)+9+1-(-1)-(-3)-(-4)=38$$$。
帮助西蒙斯找到最大值 美女 在所有 不错 重建的 重建。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5\cdot 10^4$$$)。测试用例的描述如下。
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\le n,m\le 2\cdot 10^5$$$; $$$n\cdot m\le 4\cdot 10^5$$$) — 行数和列数。
在接下来的 $$$n-1$$$ 行中,每行包含 $$$m$$$ 整数 $$$w_{i,j}$$$ ($$$-10^9\le w_{i,j}\le 10^9$$$) — $$$(i,j)$$$ 和 $$$(i+1,j)$$$ 之间街道的权重。
在接下来的 $$$n$$$ 行中,每行包含 $$$m-1$$$ 整数 $$$v_{i,j}$$$ ($$$-10^9\le v_{i,j}\le 10^9$$$) — $$$(i,j)$$$ 和 $$$(i,j+1)$$$ 之间街道的权重。
在接下来的 $$$n-1$$$ 行中,每行包含 $$$m$$$ 个字符 $$$p_{i,j}$$$ ($$$p_{i,j}\in\{\texttt{0},\texttt{1}\}$$$) — 如果 $$$p_{i,j}=\texttt{0}$$$ 之间的街道$$$(i,j)$$$ 和 $$$(i+1,j)$$$ 无法重构,反之亦然。
在接下来的 $$$n$$$ 行中,每行包含 $$$m-1$$$ 个字符 $$$q_{i,j}$$$ ($$$q_{i,j}\in\{\texttt{0},\texttt{1}\}$$$) — 如果 $$$q_{i,j}=\texttt{0}$$$,则$$$(i,j)$$$ 和 $$$(i,j+1)$$$ 无法重构,反之亦然。
保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$4\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 最大值 美女 在所有 不错 重建的 重建。
示例
输入复制
43 42 3 -2 34 9 4 -43 4 -2-9 -5 16 -1 -3111111111111111112 44 23 1 356 12 -17-14 1 -4001000001013 31 0 10 1 01 00 10 01101111011113 413 7 6 -123 -5 12 -6-3 10 -15-5 8 -1110 0 -511110110110101010
输出复制
38048
注意
第一个测试用例在语句中进行了解释。
在第二个测试用例中,只有一个 不错 重建的 重建:西蒙斯重建没有街道。所以最大 美女 是 $$$0$$$。