Collect the Maximum Treasures

You are given an \(m \times n\) grid where each cell contains one of the following values:

• 0: an empty cell
• -1: an obstacle
• A positive integer: representing the number of treasures in that cell

Your task is to determine the maximum number of treasures that can be collected when moving from the top-left cell to the bottom-right cell. You may only move either right or down at each step. If either the starting or the destination cell is an obstacle, or if there is no valid path, the result must be 0.

The solution is based on dynamic programming using the recurrence:

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

where \(dp[i][j]\) represents the maximum treasures that can be collected upon reaching cell \((i,j)\), given that the cell is not an obstacle.

inputFormat

The input is read from stdin and is formatted as follows:

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

outputFormat

Output a single integer to stdout which is the maximum number of treasures that can be collected along a valid path from the top-left to the bottom-right cell.

## sample

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

6