Cow Pie Treasures

The cows have been busily baking pies stuffed with gold coins! Each pie holds some number $N_i$ of gold coins ($1 \le N_i \le 25$), and that count is neatly written on its crust.

The cows arranged the pies in a grid of $R$ rows and $C$ columns ($1 \le R \le C \le 100$) out in the pasture. You start at the top-left pie, position (row $1$, column $1$), and immediately collect its coins. You must travel to the far side of the pasture, moving exactly one column to the right on every step, and you must finish at position (row $R$, column $C$).

When you step into the next column you may keep the same row or change your row by at most $1$: from $(r, c)$ you may move to $(r-1, c+1)$, $(r, c+1)$, or $(r+1, c+1)$. You must never leave the grid, and your path must end at (row $R$, column $C$). Every pie you land on adds its coins to your total.

Given the pasture, what is the greatest number of gold coins you can gather?

For example, consider this pasture:

6 5 3 7 9 2 7
2 4 3 5 6 8 6
4 9 9 9 1 5 8

The path below collects $6 + 4 + 9 + 9 + 6 + 5 + 8 = 47$ coins:

start-> 6 5 3 7 9 2 7
         \
        2 4 3 5 6 8 6
           \   / \
        4 9 9-9 1 5-8 <-end

The next path is even better, collecting $6 + 4 + 9 + 9 + 6 + 8 + 8 = 50$ coins, which is the most possible:

start-> 6 5 3 7 9 2 7
         \
        2 4 3 5 6-8 6
           \   /   \
        4 9 9-9 1 5 8 <-end

• Line 1: Two space-separated integers, $R$ and $C$.
• Lines 2 through $R+1$: Each line contains the $C$ coin counts of that row, space-separated and in order.

• Line 1: A single integer, the maximum number of gold coins that can be gathered.