Air Strike Blockade

Before the enemy moves, you must perform an air strike to turn some empty cells into impassable obstacles while avoiding bombing cells that contain enemy units. Due to varying terrain, each empty cell requires a different amount of explosives to be rendered impassable. Your task is to compute the minimum amount of explosives required so that no enemy unit can reach the border of the map.

The map is given as a grid with n rows and m columns. An integer of -1 indicates that the cell is occupied by an enemy (and cannot be bombed), while a non‐negative integer indicates an empty cell that can be bombed at the given cost.

This problem can be modeled as a minimum vertex cut problem on a grid. Transform each cell into two nodes (an in-node and an out-node) connected by an edge whose capacity is the bomb cost for that cell (or infinity for enemy cells). Then, for every adjacent pair of cells (sharing one of the four directions), add an edge from the out‐node of one to the in‐node of the other with infinite capacity. Finally, connect the source to each enemy cell (their in‐node) with infinite capacity and every border cell (their out‐node) to the sink with infinite capacity. The answer is the value of the minimum cut between the source and sink.

If no enemy exists, output 0. If it is impossible to block all enemy paths, output -1.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 100), representing the number of rows and columns in the grid.

Each of the next n lines contains m integers. A value of -1 indicates a cell occupied by an enemy unit (which cannot be bombed), while a non-negative integer indicates an empty cell with the cost required to bomb it and make it impassable.

outputFormat

Output a single integer: the minimum total bomb cost to prevent any enemy unit from reaching the border of the map. If it is impossible to block all escape paths, output -1.

sample

3 3
1 2 3
4 -1 6
7 8 9

20