Maximum Energy Path

You are given a grid of size \(n \times m\) where each cell contains a non-negative integer representing energy units. A robot starts at the top-left corner \((1,1)\) and needs to reach the bottom-right corner \((n,m)\). The robot can only move either to the right or downward.

Determine the maximum energy that can be collected along a path from the starting cell to the destination. The sum of the energies along the path is calculated as follows:

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

where \(\text{dp}[i][j]\) represents the maximum energy collected when reaching cell \((i,j)\). Note that the first row and the first column can only be reached by a single path.

inputFormat

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

Each of the following \(n\) lines contains \(m\) space-separated integers representing the energy values in the grid.

outputFormat

Output a single integer, the maximum energy that can be collected from the top-left to the bottom-right cell.

3 3
1 3 1
1 5 1
4 2 1

12