Maximum Candies Collection

You are given a grid of integers where each cell represents the number of candies available at that location. You start from the top-left cell and need to travel to the bottom-right cell. At each step, you may only move either to the right or down.

Your task is to collect the maximum number of candies possible along a valid path. The recurrence relation used to compute the maximum candies collected at cell \( (i,j) \) is given by:

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

Note:

• If there is only one row or one column, the answer is simply the sum of that row or column.
• Consider all valid paths, and output the maximum candies that can be collected.

inputFormat

The first line contains two space-separated integers \(N\) and \(M\) representing the number of rows and columns of the grid respectively. The next \(N\) lines contain \(M\) space-separated integers, indicating the number of candies in each cell.

outputFormat

Output a single integer, which is the maximum number of candies 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