Maximum Coins in a Grid

You are given a grid with \( N \) rows and \( M \) columns. Each cell of the grid contains a non-negative integer representing the number of coins available at that cell.

Your task is to compute the maximum number of coins that can be collected when traveling from the top-left corner (cell \( (1,1) \)) to the bottom-right corner (cell \( (N,M) \)). You are only allowed to move either right or down at any step.

This problem can be formally defined using a dynamic programming approach. Let \( dp[i][j] \) denote the maximum coins that can be collected when reaching cell \( (i,j) \). Then, for \( i \geq 1 \) and \( j \geq 1 \), the following recurrence holds:

\( dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j] \)

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two integers \( N \) and \( M \), representing the number of rows and columns of the grid, respectively.
• The next \( N \) lines each contain \( M \) space-separated integers, representing the coins in each cell of the grid.

outputFormat

Output a single integer to standard output (stdout) — the maximum number of coins that can be collected on a valid path from the top-left corner to the bottom-right corner.

1 1
5

5