P3866 [TJOI2009] 战争游戏

小 R 正在玩一个战争游戏。游戏地图是一个 $M$ 行 $N$ 列的矩阵，每个格子可能是障碍物，也可能是空地，在游戏开始时有若干支敌军分散在不同的空地格子中。每支敌军都可以从当前所在的格子移动到四个相邻的格子之一，但是不能移动到包含障碍物的格子。如果敌军移动出了地图的边界，那么战争就失败了。

现在你的任务是，在敌军开始移动前，通过飞机轰炸使得某些原本是空地的格子变得不可通行，这样就有可能阻止敌军移出地图边界（出于某种特殊的考虑，你不能直接轰炸敌军所在的格子）。由于地形不同的原因，把每个空地格子轰炸成不可通行所需的炸药数目可能是不同的，你需要计算出要阻止敌军所需的最少的炸药数。

输入文件的第一行包含两个数 $M$ 和 $N$，分别表示矩阵的长和宽。接下来 $M$ 行，每行包含用空格隔开的 $N$ 个数字，每个数字表示一个格子的情况：若数字为 $-1$，表示这个格子是障碍物；若数字为 $0$，表示这个格子里有一支敌军；若数字为一个正数 $x$，表示这个格子是空地，且把它轰炸成不可通行所需的炸药数为 $x$。 地图上的敌军数量不一定为 $1$，即地图上可能有多个 $0$。

输出一个数字，表示所需的最少炸药数。数据保证有解存在。

对 $50\%$ 的数据，$1\le M,N\le 10$。 对 $100\%$ 的数据，$1\le M,N\le 30$。 矩阵里的每个数不超过 $100$。