CF2205F.Simons and Reconstructing His Roads

Dropping all the time, but the exit I can find.

— SHUN, DYING FOR YOU

There are $n \times m$ crossroads in the city, named crossroad $(1, 1), (1, 2),\ldots, (n, m)$. The first number represents the row, and the second represents the column.

There exists and only exists streets between $(i,j)$ and $(i+1,j)$ or between $(i,j)$ and $(i,j+1)$. The street between $(i, j)$ and $(i + 1, j)$ has a weight of $w_{i,j}$, and the street between $(i, j)$ and $(i, j + 1)$ has a weight of $v_{i,j}$.

Simons wants some streets reconstructed. Due to some accidents, some of the streets cannot be reconstructed, while others are optional to be reconstructed.

For each crossroad, if the number of reconstructed streets adjacent to it is even, Simons calls the crossroad elegant. If all the crossroads are elegant, Simons calls the reconstruction nice.

The beauty of a reconstruction is calculated as follows:

• At first, the beauty is $0$.
• For each row $i$ from $1$ to $n - 1$, let the columns of the streets reconstructed be $c_1 \lt c_2 \lt c_3 \lt \cdots$, add $w_{i, c_1} - w_{i, c_2} + w_{i, c_3} - w_{i, c_4}+\cdots$ to the beauty.
• Similarly, for each column $j$ from $1$ to $m - 1$, let the rows of the streets reconstructed be $r_1 \lt r_2 \lt r_3 \lt \cdots$, add $v_{r_1, j} - v_{r_2, j} + v_{r_3, j} - v_{r_4, j}+\cdots$ to the beauty.

In other words, if a street is an odd-indexed one reconstructed in its row or column, add its weight to the beauty; else subtract it from the beauty.

For example, consider the streets and crossroads below without any streets that cannot be reconstructed:

We can have a nice reconstruction as follows:

The beauty of the reconstruction is $3+4+2-(-9)-(-2)+9+1-(-1)-(-3)-(-4)=38$.

Help Simons find the maximum beauty among all the nice reconstructions.

总是不断下落，但我却找不到出口。

——SHUN，《DYING FOR YOU》（链接）

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

西蒙斯希望对部分街道进行重建。但由于某些事故，部分街道不可重建，其余街道则可选择是否重建。

对于每个十字路口，若与其相邻的已重建街道数量为偶数，则西蒙斯称该十字路口为优雅的（elegant）；若所有十字路口均为优雅的，则西蒙斯称该重建方案为优美的（nice）。

一次重建方案的美感值（beauty）按如下方式计算：

• 初始时，美感值为 $0$；
• 对于每一行 $i$（$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$（$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$。

请帮助西蒙斯求出所有优美重建方案中所能达到的最大美感值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5\cdot 10^4$). The description of the test cases follows.

The first line contains two integers $n$ and $m$ ($2\le n,m\le 2\cdot 10^5$; $n\cdot m\le 4\cdot 10^5$) — the number of rows and columns.

In the next $n-1$ lines, each line contains $m$ integers $w_{i,j}$ ($-10^9\le w_{i,j}\le 10^9$) — the weights of the street between $(i,j)$ and $(i+1,j)$.

In the next $n$ lines, each line contains $m-1$ integers $v_{i,j}$ ($-10^9\le v_{i,j}\le 10^9$) — the weights of the street between $(i,j)$ and $(i,j+1)$.

In the next $n-1$ lines, each line contains $m$ characters $p_{i,j}$ ($p_{i,j}\in{\texttt{0},\texttt{1}}$) — if $p_{i,j}=\texttt{0}$, the street between $(i,j)$ and $(i+1,j)$ cannot be reconstructed, and vice versa.

In the next $n$ lines, each line contains $m-1$ characters $q_{i,j}$ ($q_{i,j}\in{\texttt{0},\texttt{1}}$) — if $q_{i,j}=\texttt{0}$, the street between $(i,j)$ and $(i,j+1)$ cannot be reconstructed, and vice versa.

It is guaranteed that the sum of $n\cdot m$ over all test cases does not exceed $4\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

For each test case, output a single integer — the maximum beauty among all the nice reconstructions.

对于每个测试用例，输出一个整数——所有优美重构中的最大美观度。

The first test case is explained in the statement.

In the second test case, there is only one nice reconstruction: Simons reconstructs no street. So the maximum beauty is $0$.

第一个测试用例已在题目描述中说明。

在第二个测试用例中，仅存在一种优美的重构方案：西蒙斯不重建任何街道。因此，最大美观度为 $0$。