1 #include<cstdio>  2   3 #include<cstdlib>  4   5 #include<cmath>  6   7 #include<cstring>  8   9 #include<algorithm> 10  11 #include<iostream> 12  13 #include<vector> 14  15 #include<map> 16  17 #include<set> 18  19 #include<queue> 20  21 #include<string> 22  23 #define inf 1000000000 24  25 #define maxn 10000+5 26  27 #define maxm 100000+5 28  29 #define eps 1e-10 30  31 #define ll long long 32  33 #define pa pair<int,int> 34  35 #define for0(i,n) for(int i=0;i<=(n);i++) 36  37 #define for1(i,n) for(int i=1;i<=(n);i++) 38  39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40  41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42  43 #define mod 1000000007 44  45 using namespace std; 46  47 inline int read() 48  49 { 50  51     int x=0,f=1;char ch=getchar(); 52  53     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54  55     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56  57     return x*f; 58  59 } 60 int  n,m,s,t,ans,tot=1,head[maxn],cur[maxn],h[maxn],q[maxn],num[105][105]; 61  62 struct edge{int go,next,v;}e[maxm]; 63 const int dx[4]={0,1,-1,0}; 64 const int dy[4]={1,0,0,-1}; 65  66 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;} 67  68 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);} 69  70 bool bfs() 71  72 { 73  74     for(int i=s;i<=t;i++)h[i]=-1; 75  76     int l=0,r=1;q[1]=s;h[s]=0; 77  78     while(l<r) 79  80     { 81  82         int x=q[++l]; 83  84         for(int i=head[x];i;i=e[i].next) 85  86          if(e[i].v&&h[e[i].go]==-1) 87  88          { 89  90             h[e[i].go]=h[x]+1;q[++r]=e[i].go; 91  92          } 93  94     } 95  96     return h[t]!=-1; 97  98 } 99 100 int dfs(int x,int f)101 102 {103 104     if(x==t) return f;105 106     int tmp,used=0;107 108     for(int i=cur[x];i;i=e[i].next)109 110      if(e[i].v&&h[e[i].go]==h[x]+1)111 112     {113 114         tmp=dfs(e[i].go,min(e[i].v,f-used));115 116         e[i].v-=tmp;if(e[i].v)cur[x]=i;117 118         e[i^1].v+=tmp;used+=tmp;119 120         if(used==f)return f;       121 122     }123 124     if(!used) h[x]=-1;125 126     return used;127 128 }129 130 void dinic()131 132 {133 134     while(bfs())135 136     {137 138         for (int i=s;i<=t;i++)cur[i]=head[i];ans-=dfs(s,inf);139 140     }141 142 }143 144 int main()145 146 {147 148     freopen("input.txt","r",stdin);149 150     freopen("output.txt","w",stdout);151 152     n=read();m=read();s=0;t=n*m+1;153     for1(i,n)for1(j,m)154     {155         int x=read();156         num[i][j]=(i-1)*m+j;ans+=x;157         if((i+j)&1)insert(s,num[i][j],x);else insert(num[i][j],t,x);158     }159     for1(i,n)for1(j,m)if((i+j)&1)160         for0(k,3)161         {162             int x=i+dx[k],y=j+dy[k];163             if(x<1||x>n||y<1||y>m)continue;164             insert(num[i][j],num[x][y],inf);165         }166     dinic();167     printf("%d\n",ans);168 169     return 0;170 171 }