Maximum Coins Collection

Mario is in a two-dimensional grid of size \(m \times n\) where each cell contains a certain number of coins. Mario can start from any cell in the first row. From any cell \((i, j)\), he can move to one of the three adjacent cells in the next row: directly down \((i+1, j)\), diagonally left \((i+1, j-1)\), or diagonally right \((i+1, j+1)\). The task is to determine the maximum number of coins Mario can collect on his way from the top row to the bottom row.

If the grid is empty, the answer is 0. Note that the coins in the grid may be negative as well.

inputFormat

The first line of input contains two integers \(m\) and \(n\), representing the number of rows and columns in the grid, respectively. If \(m\) is 0 or \(n\) is 0, the grid is empty.

Each of the following \(m\) lines contains \(n\) space-separated integers, representing the coins in each cell of that row.

outputFormat

Output a single integer: the maximum number of coins that can be collected following the movement rules.

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

25