Monday Blues

Interview

Time limit1sMemory limit512 MB

Summary

Given an N by M grid with costly buildable cells and blocked or unbuildable cells, find the minimum total cost to cut every path from (1,1) to (N,M), or report that no placement can do it.

Level: Hard8 of 10
Topics: Graph, Minimum spanning tree, Shortest path, Implementation
Solved: No attempts yet

Problem

It is Sunday night, and the thought of going to school tomorrow is starting to hurt.

To have an excuse for skipping school, you decide to build walls on the way from home to school so that every route is blocked.

The neighborhood is a grid of $N \times M$ cells. Home is at $(1, 1)$ and school is at $(N, M)$ .

Each cell is one of three kinds:

A cell that already has a wall (written as $-2$ ).
A cell with no wall where a wall cannot be built (written as $-1$ ).
A cell with no wall where a wall can be built for a price (written as that price).

You will build walls on cells of the third kind so that no route from home to school remains. To save money, you want the total cost to be as small as possible. In some cases the routes cannot be blocked no matter where you build, and you must detect that as well.

When moving from home to school, you can only step up, down, left, or right (not diagonally), and you cannot leave the grid. You cannot enter a cell that has a wall. The cells of home and school are guaranteed to be cells where a wall cannot be built.

Input

The first line contains the number of rows $N$ and the number of columns $M$ , separated by a space ( $2 \le N, M \le 300$ ).

Each of the next $N$ lines contains $M$ integers. The $j$ -th integer on the $i$ -th of these lines describes cell $(i, j)$ . $-2$ means the cell already has a wall, and $-1$ means a wall cannot be built there. An integer of $0$ or more means a wall can be built there, and the value is the cost of building it. Every cost is an integer not exceeding $10^9$ .

The cells of home and school, $(1, 1)$ and $(N, M)$ , are always given as $-1$ .

Output

Print the minimum cost to make school unreachable from home. If the routes cannot be blocked at all, print $-1$ .

Hint

In the first example, the walls can be placed as follows. # is the existing wall, * is a newly built wall, and . is a cell without a wall.

..#
.*.
.*.

Each of the two new walls costs $1$ , so the total cost is $2$ .

Examples3

Example 1
Input
```
3 3
-1 1 -2
1 1 1
1 1 -1
```
Expected output
```
2
```

Example 2

Input

5 5
-1 -1 5 -2 -2
-1 5 7 8 4
-2 5 -2 9 1
-2 8 11 2 -1
-2 9 1 -1 -1

Expected output

Example 3

Input

5 5
-1 -1 -1 -2 -2
-1 5 -1 -1 -1
-2 -2 -2 9 -1
-2 8 11 2 -1
-2 9 1 -1 -1

Expected output

-1