Maximum Sum Path in a Grid

Given an n x m grid of integers, your task is to find a path starting from any cell in the first row and reaching any cell in the last row such that the sum of the visited cells is maximized.

You can move from a cell (i, j) in the grid to one of the following cells in the next row:

• Directly below: (i+1, j)
• Diagonally left: (i+1, j-1)
• Diagonally right: (i+1, j+1)

The recurrence relation for the solution using dynamic programming is given by:

\( dp[i][j] = grid[i][j] + \max(dp[i-1][j-1],\, dp[i-1][j],\, dp[i-1][j+1]) \)

where the base case is \( dp[0][j] = grid[0][j] \) for all valid j. The final answer is the maximum value in the last row of the dp table.

inputFormat

The first line contains two integers n and m representing the number of rows and columns of the grid.

Each of the next n lines contains m integers separated by spaces, representing the rows of the grid.

Example:
3 4
1 2 3 4
5 6 7 8
9 10 11 12

outputFormat

Output a single integer which is the maximum sum that can be obtained by following the allowed moves from the first row to the last row.

## sample

3 4
1 2 3 4
5 6 7 8
9 10 11 12

24