#4356. Ceoi2014 Wall

题目描述

给出一个N*M的网格图，有一些方格里面存在城市，其中首都位于网格图的左上角。你可以沿着网络的边界走，要求你走的路线是一个环并且所有城市都要被你走出来的环圈起来，即想从方格图的外面走到任意一个城市一定要和你走的路线相交。你沿着方格的边界走是需要费用的，不同的边界费用可能不同，求最小代价。

1<=N,M<=400,走过边界的代价为正整数且不超过10^9

输入格式

输出格式

样例

样例输入

Input 1  

3 3  

1 0 0  

1 0 0  

0 0 1  

1 4 9 4  

1 6 6 6  

1 2 2 9  

1 1 1  

4 4 4  

2 4 2  

6 6 6  

  

input 2  

3 3  

1 0 1  

0 0 0  

0 1 0  

2 1 1 3  

5 6 1 1  

2 1 1 3  

2 1 1  

3 4 1  

4 1 1  

5 1 2

样例输出

output 1  

38  

  

output 2  

22

数据范围与提示