Maximum Coins Collection

You are given a grid with N rows and M columns. Each cell in the grid contains a non-negative integer representing the number of coins at that cell. Your task is to start from the top-left corner (cell (1,1)) and move to the bottom-right corner (cell (N,M)), collecting coins along the way. You are only allowed to move either right or down at each step.

Let (dp[i][j]) represent the maximum number of coins that can be collected when reaching cell ((i, j)). The recurrence relation is given by:

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

with the base condition (dp[1][1]=grid[1][1]). Your task is to compute (dp[N][M]), the maximum coins that can be collected.

Note: The indices in the explanation are 1-indexed, however, when implementing, adjust according to your language's indexing conventions.

inputFormat

The input is given via standard input (stdin). The first line contains two integers N and M, representing the number of rows and columns respectively. The following N lines each contain M non-negative integers separated by spaces representing the grid.

outputFormat

Output a single integer, which is the maximum number of coins that can be collected from the top-left to the bottom-right corner, printed to standard output (stdout).## sample

3 3
1 3 1
1 5 1
4 2 1

12