Max Codeball Collection

You are given a grid of size \(n \times m\) where each cell contains a non-negative integer representing the number of Codeballs that can be collected. Starting at the top-left cell (1,1) and moving only to the right or down, your task is to determine the maximum number of Codeballs you can collect by the time you reach the bottom-right cell (n, m).

The problem can be modeled using dynamic programming. Let \(dp[i][j]\) denote the maximum number of Codeballs that can be collected from the start cell to cell \((i+1, j+1)\). The recurrence relation is given by:

[ dp[i][j] = \max(dp[i-1][j],, dp[i][j-1]) + grid[i][j] \quad \text{for} ; i, j \ge 1 ]

For the first row and first column, note that you can only move from the left or from above respectively.

Input and Output: The input consists of two integers \(n\) and \(m\) followed by \(n\) lines, each containing \(m\) integers, representing the grid. The output is the maximum number of Codeballs that can be collected.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\), indicating the number of rows and columns in the grid respectively.

This is followed by \(n\) lines, each containing \(m\) space-separated integers, representing the grid.

outputFormat

Output a single integer: the maximum number of Codeballs that can be collected from the top-left to the bottom-right cell.

3 3
1 2 3
4 5 6
7 8 9

29