Maximum Coins Collection

You are given a grid of size \(m \times n\) in which each cell contains a certain number of coins. Bob starts from any cell in the first row and moves downwards. From a cell in position \((i, j)\), he can move to one of the following cells in the next row:

• Straight down: \((i+1, j)\)
• Diagonally left down: \((i+1, j-1)\)
• Diagonally right down: \((i+1, j+1)\)

Your task is to compute the maximum number of coins Bob can collect when he reaches the last row.

Note: The problem requires reading input from stdin and writing the answer to stdout.

inputFormat

The first line contains two space-separated integers \(m\) and \(n\), representing the number of rows and columns, respectively.

Each of the next \(m\) lines contains \(n\) space-separated integers representing the coin values in that row of the grid.

outputFormat

Output a single integer: the maximum coins Bob can collect from the top row to the bottom row.

3 3
5 1 7
4 8 2
3 4 6

21