Maximum Candies Collection

In this problem, you are given a grid of positive integers where each cell represents the number of candies at that location. You start at the top-left corner and want to reach the bottom-right corner. At each step, you may move either right or down. Your task is to collect the maximum number of candies along any such valid path.

Formally, given a grid ( A ) of dimensions ( n \times m ), you need to compute the value of ( dp[n-1][m-1] ) where ( dp[i][j] = A[i][j] + \max(dp[i-1][j], dp[i][j-1]) ) with proper handling of boundary cells.

For example, given the grid:

[ \begin{bmatrix} 1 & 3 & 1 \ 1 & 5 & 1 \ 4 & 2 & 1 \end{bmatrix} ]

The maximum candies that can be collected is 12.

inputFormat

The first line contains two integers ( n ) and ( m ) representing the number of rows and columns respectively. This is followed by ( n ) lines, each containing ( m ) space-separated integers representing the candy grid.

outputFormat

Output a single integer, the maximum number of candies that can be collected along a valid path from the top-left corner to the bottom-right corner.## sample

3 3
1 3 1
1 5 1
4 2 1

12