Maximum Path Sum in a Grid

You are given a grid with N rows and M columns, where each cell contains an integer value. Your task is to compute the maximum path sum from the top-left corner to the bottom-right corner of the grid. From any given cell, you can only move either to the right or downward. The sum is the total of the values of the cells visited on the path.

Let \(grid[i][j]\) be the value at row \(i\) and column \(j\). Define a DP table \(dp[i][j]\) where:

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

with the base case \(dp[0][0] = grid[0][0]\). Compute \(dp[N-1][M-1]\) as the answer.

inputFormat

The input is read from standard input with the following format:

• The first line contains two space-separated integers N and M, representing the number of rows and columns respectively.
• This is followed by N lines, each containing M space-separated integers, representing the grid.

outputFormat

Output a single integer to standard output representing the maximum sum achievable by following a path from the top-left to the bottom-right corner, moving only right or down.

3 3
1 3 1
1 5 1
4 2 1

12