Cheapest Path Through A Weighted Maze

A maze is a grid with rows rows and cols columns. Cell (i, j) is either blocked (marked -1, impassable) or open, in which case it has an energy cost between 0 and 1000 to enter. The top-left cell (0, 0) and the bottom-right cell (rows - 1, cols - 1) are always open. From any open cell you may move to any of the (up to four) adjacent open cells: up, down, left, or right (no diagonal moves).

Print the minimum total energy cost of a route from (0, 0) to (rows - 1, cols - 1), summing the cost of every cell visited along the way (including the start and end cells). If no such route exists, print -1 instead.

Input format

Line 1: two integers rows cols. Next rows lines: cols space-separated integers each -- -1 for a blocked cell, otherwise the energy cost of that cell.

Output format

A single integer: the minimum total energy cost of a route from the top-left to the bottom-right cell, or -1 if no route exists.

Constraints

• 1 <= rows, cols <= 200
• each cell is either -1 or an integer between 0 and 1000
• the top-left and bottom-right cells are never -1