Maximal Crystal Collection

You are given a grid of size \( N \times M \), where each cell contains a number of crystals. Your task is to compute the maximum number of crystals that can be collected when moving from the top-left cell (\(1,1\)) to the bottom-right cell (\(N,M\)). You can only move either right or down at any step.

The optimal path must accumulate the maximum possible total of crystals. Formally, if you denote \( grid[i][j] \) as the number of crystals in row \( i \) and column \( j \), starting from \( grid[0][0] \) (top-left) and moving to \( grid[N-1][M-1] \) (bottom-right), the recurrence relation for the maximum sum \( dp[i][j] \) is:

[ \begin{cases} dp[0][0] = grid[0][0], \ dp[i][0] = dp[i-1][0] + grid[i][0] \quad \text{for } i > 0, \ dp[0][j] = dp[0][j-1] + grid[0][j] \quad \text{for } j > 0, \ dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) + grid[i][j] \quad \text{for } i,j > 0. \end{cases} ]

inputFormat

The first line contains two integers \( N \) and \( M \) representing the number of rows and columns respectively.

This is followed by \( N \) lines, each containing \( M \) space-separated integers representing the grid values.

outputFormat

Output a single integer, the maximum number of crystals collectible from the top-left cell to the bottom-right cell.

3 3
1 3 1
1 5 1
4 2 1

12