P2096 Best Tourist Route

The streets in a tourist area form a grid. All east–west streets are tourist streets, and all north–south streets are boulevards. Because there are many visitors, tourist streets are one-way: on a tourist street you can only move from west to east. On boulevards, you can move either from south to north or from north to south. A Long (pinyin) plans to visit this area. His friend A Fu (pinyin) gave him advice by assigning a score to each segment between two adjacent intersections on every tourist street, indicating how worthwhile it is to visit. Each score is an integer from $-100$ to $100$. Boulevards are not scored. It is guaranteed that not all scores are negative. As shown in the figure (grid cells are tourist streets, vertical lines are boulevards):  A Long wants to know: if he starts on any tourist street and ends on any tourist street, what is the maximum possible sum of scores of all tourist street segments he traverses?

The first line contains two integers $m$ and $n$, separated by a space. Here $m$ means there are $m$ tourist streets ($1 \le m \le 100$), and $n$ means there are $(n+1)$ boulevards ($1 \le n \le 20001$). The next $m$ lines give the score information for each tourist street from north to south. Each line contains $n$ integers, representing the scores of the segments along the tourist street from west to east. Adjacent numbers in the same line are separated by a single space.

Output a single integer on one line: the total score of the best route found by your program.

Sample explanation: As shown, A Long starts at $17$ and ends at $34$, so the answer is $17-3+36+34=84$: ```plain -50 -47 +->[ 36]--+ -30 -23 | | | | [ 17]--+ -19 | -34 | -13 - 8 | | | | | | -42 +->[- 3]--+ -43 +->[ 34] -45 ``` Translated by ChatGPT 5