Maximum Apples Collection

You are given a grid with n rows and m columns. Each cell of the grid contains a positive integer representing the number of apples in that cell. Your task is to find the maximum number of apples you can collect if you start at the top-left cell (cell (1,1)) and move to the bottom-right cell (cell (n,m)), moving only right or down at each step.

The problem can be formulated using dynamic programming. Let \(dp[i][j]\) be the maximum number of apples collected to reach cell \( (i,j)\). Then, the recurrence relation is:

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

with the base case \(dp[0][0] = grid[0][0]\) and proper initialization for the first row and first column.

inputFormat

The input is read from standard input and is formatted as follows:

• The first line contains two integers \(n\) and \(m\) (the number of rows and columns).
• The following \(n\) lines each contain \(m\) integers separated by spaces, representing the number of apples in each cell of the grid.

outputFormat

Output a single integer on standard output, which is the maximum number of apples that can be collected along a valid path from the top-left corner to the bottom-right corner.

3 3
1 2 3
4 5 6
7 8 9

29