CF2205F 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$。

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

第一个测试点的解释见描述部分。 第二个测试点中，只有唯一的优美重建方案：Simons 不重建任何街道，所以最大美丽度为 $0$。 由 ChatGPT 5 翻译