Maximum Energy Collection in a Grid

You are given a grid with m rows and n columns where each cell contains a non-negative integer which represents the amount of energy available at that cell. Starting from the top-left corner (cell (1,1)) and moving only right or down, your task is to calculate the maximum energy that can be collected when reaching the bottom-right corner (cell (m,n)).

The problem can be solved using dynamic programming. Let \(dp[i][j]\) be the maximum energy that can be collected from the starting cell to cell \( (i,j) \). The recurrence relation is given by:

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

with the base case \(dp[0][0] = grid[0][0]\). Your program should read the input from stdin and print the result to stdout.

inputFormat

The first line contains two integers \(m\) and \(n\), the number of rows and columns of the grid respectively. The next \(m\) lines each contain \(n\) space-separated integers representing the grid.

Example:

3 3
1 2 3
4 5 6
7 8 9

outputFormat

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

Example:

29

## sample

3 3
1 2 3
4 5 6
7 8 9

29