Maximum Coins Collection

You are given a grid of size \(m \times n\), where each cell contains a certain number of coins. Your task is to find the maximum number of coins that Mario can collect when moving from the top-left corner of the grid (cell \( (1,1) \)) to the bottom-right corner (cell \( (m,n) \)).

Mario can only move either right or down at any step. Formally, if \(dp[i][j]\) represents the maximum coins collectable when reaching cell \( (i,j) \), then:

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

Determine the maximum coins collected when Mario reaches the bottom-right cell under these rules. It is guaranteed that the grid dimensions are at least 1.

inputFormat

The first line of input contains two integers \(m\) and \(n\), which are the number of rows and columns in the grid, respectively.

The next \(m\) lines each contain \(n\) space-separated integers representing the coins in each cell of the grid.

outputFormat

Output a single integer, which is the maximum number of coins that can be collected moving from the top-left to the bottom-right of the grid by only moving right or down.

3 4
0 3 1 1
2 0 0 4
1 5 3 1

12