Maximum Coins Collection

You are given a grid of non-negative integers where each cell represents the number of coins available at that position. Starting from the top-left corner, you can only move either right or down. Your goal is to collect the maximum number of coins by the time you reach the bottom-right corner.

The problem can be modeled using dynamic programming. Define (dp[i][j]) as the maximum coins collected up to cell ((i,j)). The recurrence is given by:

[ \displaystyle dp[i][j] = \max(dp[i-1][j],, dp[i][j-1]) + grid[i][j], \quad \text{for } i,j > 0 ]

with the appropriate initialization for the first row and column.

Input and output are handled via standard input and standard output.

inputFormat

The first line contains two integers (n) and (m) — the number of rows and columns of the grid respectively. The following (n) lines each contain (m) space-separated integers representing the grid.

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 4
0 3 1 1
2 0 0 4
1 5 3 1

12