Maximum Treasures Collection

Karen owns a grid farm composed of (m) rows and (n) columns. Each cell in the grid contains a non-negative integer representing the number of treasures available, except that (-1) indicates an obstacle through which Karen cannot pass. She starts at the top-left cell (0,0) and aims to reach the bottom-right cell ((m-1, n-1)) by only moving right or down. The task is to determine the maximum number of treasures Karen can collect along her path. If no valid path exists (i.e. if the start or destination is blocked, or obstacles block any potential route), the answer should be (-1).

A dynamic programming approach can be used where we define (dp[i][j]) as the maximum treasure sum that can be collected from the start to cell ((i, j)). The recurrence for a non-obstacle cell is:

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

if (grid[i][j] \neq -1) and the respective predecessor cell is reachable (i.e. its (dp) value is not (-1)).

inputFormat

The input is read from standard input (stdin) and consists of multiple lines. The first line contains two integers (m) and (n) separated by a space, representing the number of rows and columns respectively. This is followed by (m) lines, each with (n) integers separated by spaces, representing the grid content.

outputFormat

Output the maximum number of treasures that can be collected following a valid path from the top-left to the bottom-right cell. If no path exists, output (-1). The output should be printed to standard output (stdout).## sample

4 5
0 0 0 0 0
0 -1 0 0 10
0 -1 0 -1 0
0 0 0 0 1

11