Maximum Coins Collection

You are given a grid of non-negative integers where each cell represents the number of coins. Your task is to collect as many coins as possible while traveling from the top-left cell to the bottom-right cell of the grid. You can only move either right or down at any step.

Let the grid be represented as a matrix, and define the state \(dp[i][j]\) as the maximum number of coins that can be collected from the starting cell (0, 0) to cell \( (i, j) \). The recurrence relation is given by:

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

The final answer is \(dp[n-1][m-1]\), where \(n\) is the number of rows and \(m\) is the number of columns in the grid.

inputFormat

The input is read from standard input (stdin). The first line contains two integers n and m representing the number of rows and columns respectively. Each of the next n lines contains m space-separated integers representing the coin values in each cell of the grid.

outputFormat

Output a single integer to standard output (stdout) which is the maximum number of coins that can be collected along a valid path from the top-left to the bottom-right cell of the grid.

3 4
0 3 1 1
2 0 0 4
1 5 3 1

12