Maximum Energy Collection

You are given a grid of integers, where each cell represents the amount of energy that can be collected (or lost if negative) when the robot passes through it.

The robot starts at the top-left cell of the grid and needs to reach the bottom-right cell. At each step, the robot can move either right or down. Your task is to compute the maximum energy the robot can collect along any valid path.

Let \(grid\) be an \(n\times m\) matrix. Define \(dp(i,j)\) as the maximum energy collected to reach cell \((i,j)\). The recurrence relation is given by:

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

The answer is \(dp(n-1, m-1)\), the maximum energy collected at the bottom-right corner.

inputFormat

The first line of input contains two integers (n) and (m) representing the number of rows and columns, respectively. Each of the next (n) lines contains (m) space-separated integers representing the energy values in the grid. Input is read from standard input (stdin).

outputFormat

Output a single integer — the maximum energy that can be collected on a path from the top-left to the bottom-right cell. Output is written to standard output (stdout).## sample

3 3
1 -2 3
4 5 -6
7 8 9

29