Maximum Coins Collection

You are given an $N \times M$ grid where each cell contains a certain number of coins. Your task is to determine the maximum number of coins that can be collected when traveling from the top-left cell (position $(1,1)$) to the bottom-right cell (position $(N, M)$). At each step, you are allowed to move either right or down.

Formally, if you denote the grid as (grid) where (grid[i][j]) represents the coins at cell ((i+1, j+1)), you need to compute the maximum sum along a path from (grid[0][0]) to (grid[N-1][M-1]) with moves only to the right or down.

inputFormat

The first line of input contains two integers (N) and (M) representing the number of rows and columns of the grid respectively. This is followed by (N) lines, each containing (M) space-separated integers indicating the number of coins in each cell.

outputFormat

Output a single integer which is the maximum number of coins that can be collected from the top-left cell to the bottom-right cell.## sample

3 3
1 3 1
1 5 1
4 2 1

12