Gold Coin Pie Collection

Cows have baked pies containing gold coins and arranged them in an r × c matrix. You start at the pie at coordinate \((1, 1)\) and must reach the pie at \((r, c)\). From any pie at \((x, y)\), you can move to one of three pies at \((x-1, y+1)\), \((x, y+1)\), or \((x+1, y+1)\), provided that the row index remains within the range \([1, r]\). When you stop at a pie, you collect all the coins there. Determine the maximum number of coins you can collect if you strictly follow these rules and never leave the matrix.

Movement Rule: When at \((x, y)\), you can only move to \((x-1, y+1)\), \((x, y+1)\), or \((x+1, y+1)\).

Note: The coordinates use \(1\)-based indexing. All formulas are in LaTeX format.

inputFormat

The first line contains two integers \(r\) and \(c\), the number of rows and columns, respectively. The following \(r\) lines each contain \(c\) integers, where the \(j\)-th integer on the \(i\)-th line represents the number of coins in the pie at coordinate \((i, j)\).

outputFormat

Output a single integer: the maximum number of coins you can collect following the movement rules.

sample

3 3
1 2 3
4 5 6
7 8 9

15