A16514 | Simons and Reconstructing His Roads

一直在下落，但我总能找到出口。

—— SHUN, [DYING FOR YOU](https://open.spotify.com/track/2akBCXjdlUgpyZ4cr1t3B9)

城市中有 $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}$。

Simons 计划重建一些街道。由于一些事故，有些街道无法被重建，其他的街道可选择性重建。

对于每个路口，如果与其相邻的被重建街道条数为偶数，Simons 将该路口称为“优雅”的。如果所有路口都是优雅的，则称整个重建方案为“优美重建”。

重建方案的美丽度计算如下：

- 最开始美丽度为 $0$。
- 对于每一行 $i$ 从 $1$ 到 $n-1$，设本行被重建的街道在第 $c_1 < c_2 < c_3 < \cdots$ 列，则将 $w_{i, c_1} - w_{i, c_2} + w_{i, c_3} - w_{i, c_4} + \cdots$ 累加到美丽度中。
- 同理，对于每一列 $j$ 从 $1$ 到 $m-1$，设本列被重建的街道在第 $r_1 < r_2 < r_3 < \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$。

请你帮助 Simons，求出所有优美重建方案中美丽度的最大值。

每个测试点包含多组测试数据。第一行包含整数 $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) $ 之间的街道无法重建，反之可以重建。

保证所有测试数据中 $\sum n\cdot m \le 4\cdot 10^5$。

对于每组测试数据，输出一个整数，表示所有优美重建方案中的最大美丽度。