Max Reward Collection

You are given a 2D grid of integers representing rewards. Your task is to collect the maximum reward by moving from the top-left cell to the bottom-right cell. At each cell, you can only move either right or down.

The problem can be formulated using dynamic programming. Let \(dp[i][j]\) denote the maximum reward you can collect from the starting cell (0,0) to cell (i,j). The recurrence relation is given by:

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

with the appropriate base cases for the first row and the first column.

Design an algorithm to compute \(dp[m-1][n-1]\) where \(m\) is the number of rows and \(n\) is the number of columns in the grid.

inputFormat

The first line of input contains two integers \(m\) and \(n\) (the number of rows and columns respectively). The following \(m\) lines each contain \(n\) integers separated by spaces, which represent the grid.

For example:

3 3
1 2 3
4 5 6
7 8 9

outputFormat

Output a single integer, which is the maximum reward that can be collected from the top-left to the bottom-right corner following the allowed moves.

## sample

3 3
1 2 3
4 5 6
7 8 9

29