Taco: Maximum Coins Collection

David loves coins and he has discovered a treasure grid full of them! The grid consists of \(n\) rows and \(m\) columns, and each cell contains a certain number of coins. Starting from any cell in the first row, David collects the coins and moves to the next row. In each move, he may travel directly downwards, diagonally left-down, or diagonally right-down (if such moves are within the bounds of the grid).

The problem is to determine the maximum number of coins David can collect when he reaches any cell in the bottom row. The recurrence relation for this problem is given by: $$dp[i][j] = grid[i][j] + \max\begin{cases} dp[i-1][j],\\ dp[i-1][j-1] \; (if\ j>0),\\ dp[i-1][j+1] \; (if\ j<m-1) \end{cases}$$ where \(dp[i][j]\) represents the maximum coins collected up to cell \((i,j)\).

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) representing the number of rows and columns, respectively. The following \(n\) lines each contain \(m\) integers, where the \(j\)-th integer of the \(i\)-th line represents the number of coins in the cell at row \(i\) and column \(j\).

outputFormat

Output a single integer — the maximum number of coins that can be collected by starting from any cell in the first row and moving to a cell in the last row based on the allowed moves.

3 3
1 2 3
6 5 4
7 8 9

17