Maximum Path Sum in a Grid

You are given an m x n grid of integers. Your task is to find a path from the top-left corner to the bottom-right corner such that the sum of the numbers along the path is maximized. At any point, you may move either to the right or downward.

The problem can be formulated using dynamic programming. Let \(dp[i][j]\) represent the maximum sum obtainable to reach cell \((i,j)\). Then, the recurrence is given by:

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

with the boundary conditions:

• \(dp[0][0] = grid[0][0]\)
• For the first row: \(dp[0][j] = dp[0][j-1] + grid[0][j]\) for \(j \ge 1\)
• For the first column: \(dp[i][0] = dp[i-1][0] + grid[i][0]\) for \(i \ge 1\)

Your program should read the grid from standard input and then output the maximum sum obtainable along any valid path.

inputFormat

The first line of input contains two integers, \(m\) and \(n\), representing the number of rows and columns in the grid, respectively.

The next \(m\) lines each contain \(n\) integers separated by spaces, representing the grid values.

Example:

3 3
1 3 1
1 5 1
4 2 1

outputFormat

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

Example:

12

## sample

3 3
1 3 1
1 5 1
4 2 1

12