Maximum Path Sum in a Grid

You are given a grid of size N × M where each cell contains an integer. Your task is to find the maximum possible sum of elements along any path from the top-left corner (cell (1, 1)) to the bottom-right corner (cell (N, M)). From any cell, you are only allowed to move either to the right or downward.

The problem can be formulated as finding the maximum sum along a path where you add the values from the grid cells as you progress. The recurrence relation for dynamic programming is:

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

The starting cell is initialized as \( dp[0][0] = grid[0][0] \) and the answer is found at the cell \( dp[N-1][M-1] \). This method guarantees the optimal path sum under the movement constraints.

inputFormat

The first line of input contains two integers, N and M, representing the number of rows and columns of the grid respectively.

Each of the following N lines contains M integers, representing the elements of the grid. The integers on each line are separated by spaces.

outputFormat

Output a single integer representing the maximum path sum from the top-left cell to the bottom-right cell.

3 3
1 2 3
4 5 6
7 8 9

29