Description

The seating chart of Class 1 in Grade 10 is an $n\times m$ matrix. After one semester together, every student has become good friends with the students adjacent in the four directions (up, down, left, right). This semester, they need to split into liberal arts and science. Each student has their own happiness value for choosing liberal arts or science, and for each pair of friends, if they both choose liberal arts or both choose science, they will gain some extra happiness.

scp, the big boss and coach of programming contests, wants to know how to assign choices to maximize the class’s total happiness.

Input Format

The first line contains two positive integers $n$, $m$.

Then follow six matrices.

• The first matrix has $n$ rows and $m$ columns. The number at row $i$, column $j$ is the happiness the student at row $i$, column $j$ gets for choosing liberal arts.
• The second matrix has $n$ rows and $m$ columns. The number at row $i$, column $j$ is the happiness the student at row $i$, column $j$ gets for choosing science.
• The third matrix has $n-1$ rows and $m$ columns. The number at row $i$, column $j$ is the extra happiness if the student at row $i$, column $j$ and the student at row $i+1$, column $j$ both choose liberal arts.
• The fourth matrix has $n-1$ rows and $m$ columns. The number at row $i$, column $j$ is the extra happiness if the student at row $i$, column $j$ and the student at row $i+1$, column $j$ both choose science.
• The fifth matrix has $n$ rows and $m-1$ columns. The number at row $i$, column $j$ is the extra happiness if the student at row $i$, column $j$ and the student at row $i$, column $j+1$ both choose liberal arts.
• The sixth matrix has $n$ rows and $m-1$ columns. The number at row $i$, column $j$ is the extra happiness if the student at row $i$, column $j$ and the student at row $i$, column $j+1$ both choose science.

Output Format

Output a single integer, the maximum possible total happiness.

1 2
1 1
100 110
1
1000

1210

Hint

Sample Explanation

If both choose science, they obtain $100+110+1000$ in happiness.

For $100\%$ of the testdata, $1\le n,m \le 100$, and all happiness values are non-negative integers not exceeding $5000$.

Translated by ChatGPT 5