Maximum Gems Collection in a Grid

You are given a grid with N rows and M columns, where each cell contains a certain number of gems. Starting from the top-left corner (cell (1,1)) and moving only to the right or down, your task is to compute the maximum number of gems that can be collected when reaching the bottom-right corner (cell (N,M)).

The problem can be modeled using dynamic programming. The recurrence relation is given by:

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

with appropriate initialization for the first row and first column.

Note: The grid indices in the above formula are 1-indexed for explanation purposes. In your implementation, adjust the indices accordingly if you use 0-based indexing.

inputFormat

The first line contains two integers N and M separated by a space, representing the number of rows and columns respectively.

The next N lines each contain M integers separated by spaces, where the j-th integer in the i-th line represents the number of gems in cell (i, j).

You should read the input from stdin.

outputFormat

Output a single integer representing the maximum number of gems that can be collected by moving from the top-left corner to the bottom-right corner following the allowed moves. The output should be printed to stdout.

## sample

3 3
1 2 3
4 5 6
7 8 9

29

</p>