Rare Element Collection

You are given a grid representing an excavation site where each cell holds a certain amount of a rare element. Starting from the top-left cell, you can only move either right or down in each step. Your goal is to collect the maximum possible amount of the rare element by the time you reach the bottom-right cell.

Note: The path always starts at the cell in the top-left (i.e. cell (1,1)) and ends at the bottom-right cell. At each step, you can move either to the right or down. The sum collected is the sum of all cell values visited along the path.

The problem can be solved using dynamic programming with the recurrence:

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

with appropriate initialization for the first row and column.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of rows and columns in the grid, respectively.

The following \(N\) lines each contain \(M\) integers separated by spaces, representing the grid values.

outputFormat

Output a single integer representing the maximum amount of the rare element that can be collected along any valid path from the top-left cell to the bottom-right cell.

3 4
1 3 1 8
3 2 0 4
6 1 3 2

19