Maximum Treasures Collection

You are given an (n \times m) grid representing a mansion. Each cell in the grid contains a non-negative integer indicating the number of treasures or a value of (-1) which represents an obstacle that cannot be crossed. You start from the top-left cell (cell ((1,1))) and need to reach the bottom-right cell (cell ((n,m))) by moving only to the right or downward. Your task is to compute the maximum number of treasures that can be collected along any valid path. If there is no valid path, output 0.

Note: The top-left and bottom-right cells are guaranteed not to be obstacles.

The state transition for the dynamic programming solution is given by: [ dp[i][j] = grid[i][j] + \max(dp[i-1][j],; dp[i][j-1]) ] for every accessible cell ((i,j)).

inputFormat

Input is read from standard input (stdin). The first line contains two integers (n) and (m), representing the number of rows and columns in the grid. The next (n) lines each contain (m) space-separated integers describing the grid. Each cell's value is either a non-negative integer (treasures) or (-1) (obstacle). It is guaranteed that the top-left and bottom-right cells are not obstacles.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of treasures that can be collected along a valid path from the top-left corner to the bottom-right corner. If no such path exists, output 0.## sample

3 3
1 2 -1
1 -1 3
4 2 1

9