F. Симон и восстановление дорог
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Dropping all the time, but the exit I can find.
— 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}$$$.

Симон хочет восстановить некоторые улицы. Из-за некоторых происшествий некоторые улицы не могут быть восстановлены, в то время как другие могут быть восстановлены по желанию.

Для каждого перекрестка, если количество восстановленных улиц, прилегающих к нему, чётное, Симон называет перекресток элегантным. Если все перекрестки элегантные, Симон называет восстановление приятным.

Красота восстановления рассчитывается следующим образом:

  • Сначала красота равна $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальную красоту среди всех приятных восстановлений.

Пример
Входные данные
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
Выходные данные
38
0
4
8
Примечание

Первый набор входных данных объясняется в условии.

Во втором наборе входных данных есть только одно приятное восстановление: Симон не восстанавливает ни одной улицы. Таким образом, максимальная красота равна $$$0$$$.