P1006 [NOIP 2008 Senior] Passing Notes

Xiaoyuan and Xiaoxuan are good friends and classmates who always have a lot to talk about. During a team-building activity, the class is seated in an $m$-by-$n$ grid. Xiaoyuan and Xiaoxuan are placed at opposite ends of the main diagonal, so they cannot talk directly. Fortunately, they can communicate by passing notes. The note must be relayed by several classmates: Xiaoyuan sits at the top-left corner with coordinates $(1,1)$, and Xiaoxuan sits at the bottom-right corner with coordinates $(m,n)$. A note passed from Xiaoyuan to Xiaoxuan may only move down or right; a note passed from Xiaoxuan to Xiaoyuan may only move up or left. During the activity, Xiaoyuan wants to send a note to Xiaoxuan and also receive a reply. Every classmate can help relay notes but will help at most once in total. That is, if a classmate helps when the note is sent from Xiaoyuan to Xiaoxuan, they will not help when the note is sent in the reverse direction, and vice versa. Another point to note is that each classmate has a kindness level, which varies from person to person (note: the kindness of Xiaoyuan and Xiaoxuan is undefined and is represented by $0$ in the input). Kindness is represented by a natural number in $[0,100]$, with larger numbers indicating greater kindness. Xiaoyuan and Xiaoxuan wish to choose classmates with as high kindness as possible to relay the notes, i.e., to find two relay paths (there and back) such that the sum of kindness values of classmates on these two paths is maximized. Please help them find such two paths.

The first line contains two integers $m$ and $n$ separated by a space, indicating there are $m$ rows and $n$ columns. The next $m$ lines describe an $m \times n$ matrix. The integer in row $i$, column $j$ represents the kindness of the student seated at row $i$, column $j$. The $n$ integers in each row are separated by spaces.

Output a single integer on one line, which is the maximum possible sum of kindness values of the students who participate in relaying the two notes.

- Constraints: - For $30\%$ of the testdata, $2 \le m,n \le 10$. - For $100\%$ of the testdata, $2 \le m,n \le 50$. - Problem Source: NOIP 2008 Senior, Problem 3. Translated by ChatGPT 5