Minimum Path Cost in a Grid with Obstacles

Given a grid with (m) rows and (n) columns, where each cell contains an integer. A cell with a non-negative number represents the cost of stepping on that cell, while a cell with (-1) represents an obstacle that cannot be traversed. Your task is to find the minimum cost path from the top-left cell (0,0) to the bottom-right cell (m-1,n-1) by only moving right or down. If no such path exists, output (-1). The cost of a path is defined as the sum of the costs of all visited cells. For example, if the grid is given by [ \begin{bmatrix} 1 & 2 & 3 \ 4 & -1 & 5 \ 3 & 2 & 1 \end{bmatrix} ] then one valid path is (0,0) (\to) (1,0) (\to) (2,0) (\to) (2,1) (\to) (2,2) with a total cost of (1+4+3+2+1=11).

inputFormat

The input is read from stdin. The first line contains two integers (m) and (n), representing the number of rows and columns respectively. This is followed by (m) lines, each containing (n) space-separated integers representing the cells of the grid.

outputFormat

Output a single integer to stdout representing the minimum cost to travel from the top-left cell to the bottom-right cell. If no valid path exists, output (-1).## sample

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

11