Maximum Sum Path in a Matrix

You are given a matrix of integers. Your task is to find the maximum possible sum along a path from the top-left corner to the bottom-right corner of the matrix. You can only move either to the right or downward at any step.

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

[ \begin{aligned} dp[i][j] &= \max(dp[i-1][j],, dp[i][j-1]) + matrix[i][j] \quad (i > 0, j > 0), \ \text{with } dp[0][j] &= dp[0][j-1] + matrix[0][j] \quad (j > 0), \ \text{and } dp[i][0] &= dp[i-1][0] + matrix[i][0] \quad (i > 0). \end{aligned} ]

The answer is the value of \(dp[n-1][m-1]\) where \(n\) is the number of rows and \(m\) is the number of columns.

inputFormat

The input is read from stdin and has the following format:

N M
row1_element1 row1_element2 ... row1_elementM
row2_element1 row2_element2 ... row2_elementM
...
rowN_element1 rowN_element2 ... rowN_elementM

where N is the number of rows and M is the number of columns in the matrix.

outputFormat

Output the maximum sum path value as a single integer to stdout.

3 3
1 2 3
4 5 6
7 8 9

29