Maximum Coins Collection

You are given a grid of integers (grid) with (n) rows and (m) columns. Each cell of the grid contains an integer representing the coins in that cell. Your task is to determine the maximum number of coins that can be collected when moving from the top-left corner to the bottom-right corner of the grid. You are only allowed to move either right or down at any step.

The solution is based on dynamic programming. Let (dp[i][j]) denote the maximum number of coins that can be collected reaching cell ((i+1, j+1)) (here using 1-indexed notation). The recurrence relation is given by: [ dp[i][j] = \max(dp[i-1][j],, dp[i][j-1]) + grid[i][j] ] for (i, j > 0), with appropriate initialization for the first row and first column. Note that the grid may contain negative values as well.

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, which denote the coins present in each cell of the grid.

outputFormat

Output a single integer which is the maximum number of coins that can be collected on 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