Maximum Coins Collection in a Grid

You are given a grid of non-negative integers with N rows and M columns. Each cell of the grid contains some coins. You need to find the maximum number of coins you can collect if you start at the top-left cell (first row, first column) and move to the bottom-right cell (last row, last column) of the grid. You are only allowed to move either to the right or down at any step.

The problem can be formulated using dynamic programming. Let \(dp[i][j]\) represent the maximum coins that can be collected when reaching cell \((i, j)\). The recurrence is given by:

[ dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j], \quad 1 \leq i < N,; 1 \leq j < M ]

with the boundary conditions:

[ dp[0][0] = grid[0][0], \quad dp[i][0] = dp[i-1][0] + grid[i][0] \quad (i \geq 1), \quad dp[0][j] = dp[0][j-1] + grid[0][j] \quad (j \geq 1). ]

Your task is to implement an efficient solution that computes the maximum coins collected along any valid path from the top-left to the bottom-right of the grid.

inputFormat

The first line of input contains two space-separated integers, N and M representing the number of rows and columns of the grid respectively.

The next N lines contain M space-separated integers each, representing the coin values in each cell of the grid.

\(1 \leq N, M \leq 10^3\) and each coin value is a non-negative integer.

outputFormat

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

## sample

3 3
1 3 1
1 5 1
4 2 1

12