Maximum Treasure Collection

You are given a grid with n rows and m columns. Each cell contains a non-negative integer representing the amount of treasure. A hunter starts at the top-left corner (cell (1,1)) and needs to reach the bottom-right corner (cell (n,m)). The hunter can only move either right or down at any step.

Your task is to compute the maximum amount of treasure the hunter can collect along such a path.

The relation used in the dynamic programming solution is given by:

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

where \(dp[i][j]\) represents the maximum treasure that can be collected from the start to cell \( (i,j) \). For the first row and first column, only one move is possible (either right or down).

inputFormat

The first line of input contains two integers n and m, representing the number of rows and columns of the grid, respectively. The next n lines each contain m integers separated by spaces, where each integer represents the treasure in that cell.

outputFormat

Output a single integer which is the maximum treasure that can be collected from the top-left to the bottom-right of the grid.

3 3
1 3 1
1 5 1
4 2 1

12