Maximum Coins Path

You are given a matrix of integers where each cell represents the number of coins available. Starting from the top-left corner, you can move either to the right or down. Your task is to determine the maximum number of coins you can collect by the time you reach the bottom-right corner.

The dynamic programming recurrence used to solve this problem is given by:

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

where \(a_{ij}\) is the number of coins at cell \((i,j)\). It is guaranteed that the matrix has at least one cell.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the number of rows and columns of the matrix, respectively. This is followed by \(n\) lines, each containing \(m\) space-separated integers. The \(j^{th}\) integer in the \(i^{th}\) line represents \(a_{ij}\), the number of coins in cell \((i, j)\).

outputFormat

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

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

12