Maximizing Collected Coins

You are given a grid of size N x M filled with coin values (either 0 or 1). A player starts at the top-left corner (cell (0,0)) and must move to the bottom-right corner (cell (N-1, M-1)). The player is only allowed to move either right or down at any step. Your task is to determine the maximum number of coins that the player can collect while moving from the start to the finish.

The problem can be modeled using dynamic programming.

DP Recurrence:

Let \( dp[i][j] \) represent the maximum number of coins collected to reach cell \( (i, j) \). Then, the recurrence is given by:

[ \begin{aligned} dp[0][0] &= grid[0][0], \ \text{For } j \ge 1: \quad dp[0][j] &= dp[0][j-1] + grid[0][j], \ \text{For } i \ge 1: \quad dp[i][0] &= dp[i-1][0] + grid[i][0], \ \text{For } i, j \ge 1: \quad dp[i][j] &= \max{ dp[i-1][j],\ dp[i][j-1] } + grid[i][j]. \end{aligned} ]

The final answer will be stored in \( dp[N-1][M-1] \).

inputFormat

The first line contains two integers N and M separated by a space.

Each of the next N lines contains M integers (0 or 1) separated by spaces representing the grid.

outputFormat

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

## sample

3 4
1 0 0 1
0 1 0 0
1 0 0 1

3