F. Simons and Reconstructing His Roads
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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

Example
Input
4
3 4
2 3 -2 3
4 9 4 -4
3 4 -2
-9 -5 1
6 -1 -3
1111
1111
111
111
111
2 4
4 23 1 35
6 12 -17
-14 1 -40
0100
000
101
3 3
1 0 1
0 1 0
1 0
0 1
0 0
110
111
10
11
11
3 4
13 7 6 -12
3 -5 12 -6
-3 10 -15
-5 8 -11
10 0 -5
1111
0110
110
101
010
Output
38
0
4
8
Note

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$$$.