P1646 [CTT] happiness

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.

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 a single integer, the maximum possible total happiness.

### 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