Maximum Gold Collection

In this problem, you are given a grid with (N) rows and (M) columns. Each cell of the grid contains a certain number of gold coins. Starting from the top-left cell at position ((0,0)), your goal is to reach the bottom-right cell at position ((N-1, M-1)) by only moving right or down. Along the way, you collect all the gold coins present in the cells you visit.

Formally, given a two-dimensional array (grid), you need to find the maximum sum of coins you can collect. The dynamic programming recurrence is given by:
(dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j]), with appropriate boundary conditions.

inputFormat

The first line of input contains two integers (N) and (M) indicating the number of rows and columns, respectively. This is followed by (N) lines, each containing (M) space-separated integers representing the number of coins in each cell of the grid.

outputFormat

Output a single integer representing the maximum number of gold coins that can be collected from the top-left cell to the bottom-right cell.## sample

3 3
1 3 1
1 5 1
4 2 1

12