Maximum Apples Path

You are given a grid with R rows and C columns where each cell contains a number representing the number of apples. Starting from the top-left corner (1,1), you want to collect as many apples as possible while moving only to the right or down, and finish at the bottom-right corner (R,C).

The following recurrence relation applies to any cell \( (i,j) \) (with 1-indexing):

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

Compute and output the maximum number of apples that can be collected.

inputFormat

The first line contains two integers R and C separated by space, representing the number of rows and columns of the grid, respectively.

Each of the following R lines contains C integers separated by spaces, representing the grid values.

outputFormat

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

3 3
1 2 3
4 5 6
7 8 9

29