Taco Resource Collection

You are given a grid of size \(m \times n\). Each cell in the grid contains an integer that represents the resources available at that location. A cell with a value of -1 denotes an obstacle that cannot be traversed.

The robot starts at the top-left cell (first row, first column) and aims to reach the bottom-right cell (\(m\)th row, \(n\)th column). The robot can only move either right or down at each step. Your task is to compute the maximum amount of resources that the robot can collect along any valid path from the start to the goal. If there is no valid path, output -1.

The state transition for the dynamic programming solution is given by:

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

with the condition that if a cell is an obstacle, i.e. \(grid[i][j] = -1\), then \(dp[i][j]\) is set to \(-1\) and the cell cannot be used in the path.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case:
• The first line contains two integers \(m\) and \(n\), representing the number of rows and columns of the grid respectively.
• The next \(m\) lines each contain \(n\) space-separated integers where each integer indicates the resource value at that cell (or -1 for an obstacle).

outputFormat

For each test case, output a single integer on a new line representing the maximum number of resources that the robot can collect from the top-left to the bottom-right corner. If there is no valid path, output -1.

## sample

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

4
-1

</p>