Maximum Path Sum in a Grid

You are given an n x m grid filled with non-negative integers. Your task is to compute the maximum possible sum along a path from the top-left corner to the bottom-right corner of the grid. You can only move either right or down at any step.

The value at each cell is added to the path sum. Formally, define a DP table dp where the recurrence is given by:

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

with the initial condition \( dp[0][0] = grid[0][0] \). Your goal is to compute \( dp[n-1][m-1] \).

Example: For grid:

1 3 1
1 5 1
4 2 1

The maximum path sum is 12.

inputFormat

The first line of the input contains two integers n and m (the number of rows and columns, respectively). The following n lines each contain m space-separated integers representing the grid.

For example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

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

For example, the output for the above input is:

12

## sample

3 3
1 3 1
1 5 1
4 2 1

12