Maximum Path Sum in a Grid

You are given an m x n grid filled with integers. Your task is to find the maximum sum of reward points you can collect by starting at the top-left cell and moving to the bottom-right cell. At each step, you can only move either to the right or down.

The problem can be formulated with the following recurrence relation in LaTeX format:

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

The answer is \(dp[m-1][n-1]\).

inputFormat

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

<m> <n>
row_1
row_2
...
row_m

Here, the first line contains two space-separated integers: m (number of rows) and n (number of columns). Each of the next m lines contains n space-separated integers representing the grid.

outputFormat

Output to standard output (stdout) a single integer, which is the maximum path sum from the top-left to the bottom-right of the grid.

3 3
1 2 3
4 5 6
7 8 9

29