cho.sh

Monday Blues

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.

Hard8GraphMinimum spanning treeShortest pathImplementationInterviewNo attempts yetTime limit1sMemory limit512 MB

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×MN \times M cells. Home is at (1,1)(1, 1) and school is at (N,M)(N, M).

Each cell is one of three kinds:

  • A cell that already has a wall (written as −2-2).
  • A cell with no wall where a wall cannot be built (written as −1-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 NN and the number of columns MM, separated by a space (2≤N,M≤3002 \le N, M \le 300).

Each of the next NN lines contains MM integers. The jj-th integer on the ii-th of these lines describes cell (i,j)(i, j). −2-2 means the cell already has a wall, and −1-1 means a wall cannot be built there. An integer of 00 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 10910^9.

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

Output

Print the minimum cost to make school unreachable from home. If the routes cannot be blocked at all, print −1-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 11, so the total cost is 22.