#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define N 3000
#define M 10000
#define inf 1073741824
#define ll int
//N为点数 M为边数
struct Edge{
int from, to, cap, nex;
}edge[M*10];//注意这个一定要够大 不然会re 还有反向弧
int head[N], edgenum;
void addedge(int u, int v, ll cap){
Edge E = { u, v, cap, head[u]};
edge[ edgenum ] = E;
head[u] = edgenum ++;
Edge E2= { v, u, 0, head[v]};
edge[ edgenum ] = E2;
head[v] = edgenum ++;
}
int sign[N], s, t;
bool BFS(int from, int to){
memset(sign, -1, sizeof(sign));
sign[from] = 0;
queue<int>q;
q.push(from);
while( !q.empty() ){
int u = q.front(); q.pop();
for(int i = head[u]; i!=-1; i = edge[i].nex)
{
int v = edge[i].to;
if(sign[v]==-1 && edge[i].cap)
{
sign[v] = sign[u] + 1, q.push(v);
if(sign[to] != -1)return true;
}
}
}
return false;
}
int Stack[M*4], top, cur[M*4];
ll dinic(){
ll ans = 0;
while( BFS(s, t) )
{
memcpy(cur, head, sizeof(head));
int u = s; top = 0;
while(1)
{
if(u == t)
{
ll flow = inf;int loc;//loc 表示 Stack 中 cap 最小的边
for(int i = 0; i < top; i++)
if(flow > edge[ Stack[i] ].cap)
{
flow = edge[Stack[i]].cap;
loc = i;
}
for(int i = 0; i < top; i++)
{
edge[ Stack[i] ].cap -= flow;
edge[Stack[i]^1].cap += flow;
}
ans += flow;
top = loc;
u = edge[Stack[top]].from;
}
for(int i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增广的边的下标
if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
if(cur[u] != -1)
{
Stack[top++] = cur[u];
u = edge[ cur[u] ].to;
}
else
{
if( top == 0 )break;
sign[u] = -1;
u = edge[ Stack[--top] ].from;
}
}
}
return ans;
}
int n, m;
int idx(int x, int y){return x*m+y;}
int main(){
int i, j;
while(~scanf("%d%d",&n,&m)){
memset(head, -1, sizeof(head)), edgenum = 0;
s = n*m+1; t = s+1;
ll sum = 0, now;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
scanf("%d",&now); sum+=now;
int num = (i-1)*m+j;
if((i+j)&1)
{
addedge(s, num, now);
if(i>1) addedge(num, num-m, inf);
if(i<n) addedge(num, num+m, inf);
if(j>1) addedge(num, num-1, inf);
if(j<m) addedge(num, num+1, inf);
}
else addedge(num, t, now);
}
}
printf("%d\n", sum-dinic());
}
return 0;
}
/*
1 1
10
3 3
75 15 21
75 15 28
34 70 5
*/
HDU 1569 黑白染色+最小割