P6208 [USACO06OCT] Cow Pie Treasures G

The cows made some pies with gold coins hidden inside and arranged them into a matrix with $r$ rows and $c$ columns. Now you need to move from the pie at coordinate $(1,1)$ to the pie at coordinate $(r,c)$. For each move, you must move one column to the right, and the change in row number cannot exceed $1$. That is, if you are next to the pie at coordinate $(x,y)$, you can only move to the pie at coordinate $(x-1,y+1)$, $(x,y+1)$, or $(x+1,y+1)$. When you stop next to a pie, you can take all the gold coins in it. Of course, you do not want to leave the matrix halfway and give up those coins. The cows give you a table that lists the number of gold coins hidden in each pie in the matrix. You want to know, following the rules above, what is the maximum number of coins you can collect.

The first line contains two integers $r, c$. The next $r$ lines each contain $c$ integers, representing the number of gold coins $t$ hidden in each pie in the matrix.

One line with one integer, representing the maximum number of gold coins you can collect.

**【Constraints】** For $100\%$ of the testdata, $1 \le r, c \le 100$, $1 \le t \le 25$. ------------ **【Sample Explanation】** The matrix given in the sample is shown in the figure.  This is one valid way to move. You can collect $47$ gold coins.  In this matrix, the maximum number of gold coins you can collect is $50$, and the path is shown in the figure.  Translated by ChatGPT 5