Maximizing Gem Collection

David is on a quest to collect as many gems as possible while traversing a 2D grid. He starts at the top-left corner and must reach the bottom-right corner. At each cell, which contains a non-negative number of gems, David collects the gems from that cell. He can only move either down or to the right at any point in time.

Your task is to determine the maximum number of gems David can collect. Use a dynamic programming approach to compute the maximum gems that can be collected from the starting point to the destination.

The recurrence relation can be formulated as follows:

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

with the initial conditions set by the first row and first column.

inputFormat

The first line of input contains two integers \( m \) and \( n \) representing the number of rows and columns of the grid, respectively.

This is followed by \( m \) lines, each containing \( n \) space-separated integers, where each integer represents the number of gems at that cell.

outputFormat

Output a single integer which is the maximum number of gems David can collect while travelling from the top-left to the bottom-right of the grid.

3 3
1 3 1
1 5 1
4 2 1

12