Description

Choosing between arts and science is a very frustrating thing. (Although people who see this problem surely have never been frustrated about it.)

Student P's class is going to split into arts and science. The class can be described by an $n\times m$ matrix, where each cell represents a student's seat. Every student must choose exactly one subject: arts or science. Students will gain a satisfaction value based on their choices, computed as follows:

• If the student at row $i$, column $j$ chooses arts, they gain $art_{i,j}$ satisfaction; if they choose science, they gain $science_{i,j}$.

• If the student at row $i$, column $j$ chooses arts, and all of their adjacent classmates (two cells are adjacent if and only if they share a common edge) also choose arts, then they will be happier, so an additional $same\text{\underline{ }}art_{i,j}$ satisfaction is added.

• If the student at row $i$, column $j$ chooses science, and all of their adjacent classmates also choose science, then an additional $same\text{\underline{ }}science_{i,j}$ satisfaction is added.

Student P wants to know how everyone should choose in order to maximize the total satisfaction of all students. Please output this maximum value.

Input Format

The first line contains two positive integers $n,m$.
The next $n$ lines each contain $m$ integers; the integer in row $i$, column $j$ represents $art_{i,j}$.
The next $n$ lines each contain $m$ integers; the integer in row $i$, column $j$ represents $science_{i,j}$.
The next $n$ lines each contain $m$ integers; the integer in row $i$, column $j$ represents $same\text{\underline{ }}art_{i,j}$.
The next $n$ lines each contain $m$ integers; the integer in row $i$, column $j$ represents $same\text{\underline{ }}science_{i,j}$.

Output Format

Output a single integer, representing the maximum total satisfaction.

3 4
13 2 4 13
7 13 8 12
18 17 0 5
8 13 15 4
11 3 8 11
11 18 6 5
1 2 3 4 
4 2 3 2
3 1 0 4
3 2 3 2
0 2 2 1
0 2 4 4 

152

Hint

Sample Explanation

$1$ means choosing arts, and $0$ means choosing science. One possible plan is as follows:

1 0 0 1

0 1 0 0

1 0 0 0

Constraints

$n,m\leq 100$, and all input values are $\leq 500$.

Translated by ChatGPT 5