Maximum Gold Collection

You are given a grid of size M × N where each cell contains some amount of gold. Starting from any cell in the first column, your goal is to collect the maximum amount of gold by moving to the right in the grid. From a given cell at position (i, j), you may move in one of the following three directions:

• Right: to cell (i, j+1)
• Right-Up: to cell (i-1, j+1)
• Right-Down: to cell (i+1, j+1)

The recurrence relation used in the dynamic programming solution is given by:

$$dp[i][j] = matrix[i][j] + \max(dp[i][j+1],\; dp[i-1][j+1],\; dp[i+1][j+1])$$

Your task is to compute the maximum amount of gold that can be collected from the grid.

inputFormat

The first line of input contains two integers M and N (the number of rows and columns, respectively). Each of the following M lines contains N space-separated integers representing the grid values.

outputFormat

Output a single integer: the maximum amount of gold that can be collected following the allowed moves.## sample

3 3
1 3 3
2 1 4
0 6 4

12