Maximum Coins Collection from Grid

You are given a grid with n rows and m columns, where each cell contains a certain number of coins. Your task is to start at the top-left corner (cell (1,1)) and reach the bottom-right corner (cell (n,m)), moving only to the right or down. As you move, you accumulate the coins found in each cell. Your goal is to determine the maximum number of coins that can be collected along the way.

The problem can be formulated using dynamic programming. Let \(dp(i,j)\) represent the maximum coins that can be collected from the start to cell \((i,j)\). The recurrence relation is given by:

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

The base cases are the first row and first column, where you can only come from the left and above, respectively.

inputFormat

The first line contains two integers n and m, representing the number of rows and columns in the grid. Each of the following n lines contains m integers separated by spaces, representing the coins in each cell of the grid.

outputFormat

Output a single integer — the maximum number of coins that can be collected from the top-left corner to the bottom-right corner following the allowed moves.

## sample

1 1
5

5