Maximum Score Path

You are given a grid with n rows and m columns. Each cell of the grid contains an integer score. You can start from any cell in the first row and move downwards until you reach the last row.

At each step, if you are at position (i, j), you may move to one of the following positions in the next row:

• (i+1, j-1) (diagonally left downward),
• (i+1, j) (directly downward), or
• (i+1, j+1) (diagonally right downward).

Your task is to compute the maximum sum of scores collected along a path from the first row to the last row. The recurrence relation can be written in \( \LaTeX \) as:

[ \text{dp}[i][j] = \text{grid}[i][j] + \max\Big(\text{dp}[i-1][j-1],, \text{dp}[i-1][j],, \text{dp}[i-1][j+1]\Big) ]

where any index out of bounds is ignored.

inputFormat

The first line contains two integers n and m representing the number of rows and columns respectively. Each of the next n lines contains m space-separated integers representing the grid.

outputFormat

Output a single integer, the maximum score sum obtainable following the movement rules from the first row to the last row.

3 3
1 2 3
4 5 6
7 8 9

18