Maximum Path Sum in a Grid

Given a grid of integers with N rows and M columns, your task is to find a path from the top row to the bottom row that maximizes the sum of the numbers on the path. You can start from any cell in the first row and, from any cell at position \( (i, j) \), you can move to one of the following cells in the next row:

• \( (i+1, j) \) directly below,
• \( (i+1, j-1) \) diagonally left,
• \( (i+1, j+1) \) diagonally right.

Your goal is to reach any cell in the last row such that the sum of the visited cells is maximized. The solution must be implemented to read the input from stdin and output the result to stdout.

inputFormat

The first line contains two integers N and M representing the number of rows and columns in the grid, respectively. Each of the following N lines contains M integers separated by spaces, representing the grid.

For example:

4 4
5 3 2 4
4 7 1 2
2 3 8 1
6 1 1 5

outputFormat

Output a single integer that represents the maximum sum from the top row to the bottom row following the given movement rules.

4 4
5 3 2 4
4 7 1 2
2 3 8 1
6 1 1 5

25