Maximum Jewels Collection

You are given a grid of size (N \times M) where each cell contains a non-negative integer representing the number of jewels. Starting from the top-left cell, you can only move to the right or down until you reach the bottom-right cell. Your task is to find the path that yields the maximum sum of jewels collected along the way using a dynamic programming approach.

The optimal substructure is defined as follows: Let (dp[i][j]) denote the maximum number of jewels that can be collected up to cell ((i, j)). Then, the recurrence relation is given by:
[ dp[i][j] = \max(dp[i-1][j],; dp[i][j-1]) + grid[i][j] ]
with the initialization (dp[0][0] = grid[0][0]), and appropriate handling of the first row and column.

inputFormat

The first line contains two integers (N) and (M) separated by a space, representing the number of rows and columns of the grid. Each of the following (N) lines contains (M) space-separated integers representing the jewels in each cell.

outputFormat

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

3 3
1 2 3
4 5 6
7 8 9

29