Dinic

#include <bits/stdc++.h>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
typedef double db;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
int s,t;
struct EDGE { int v,w,nx; }lb[N<<1]; int tot=1,top[N],cur[N];
void add (int u,int v,int w)
{
    lb[++tot].v=v,lb[tot].w=w,lb[tot].nx=top[u],top[u]=tot;
    lb[++tot].v=u,lb[tot].w=0,lb[tot].nx=top[v],top[v]=tot;
}
queue <int> q;
int d[N];
bool bfs ()
{
    memset (d,0,sizeof (d));
    memcpy (cur,top,sizeof (top));
    bool ly=0;
    q.push (s),d[s]=1;
    while (q.size ())
    {
        int u=q.front (); q.pop ();
        for (int kb=top[u]; kb!=-1; kb=lb[kb].nx)
        {
            int v=lb[kb].v,w=lb[kb].w;
            //if (v<=0) continue;
            if (w&&!d[v])
            {
                d[v]=d[u]+1;
                q.push (v);
                ly|=(v==t);
            }
        }
    }
    return ly;
}
int dinic (int u,int flow)
{
    if (u==t) return flow;
    int rest=flow;
    for (; cur[u]!=-1&&rest; cur[u]=lb[cur[u]].nx)
    {
        int c=cur[u];
        int v=lb[c].v,w=lb[c].w;
        if (w&&d[v]==d[u]+1)
        {
            int k=dinic (v,min (rest,w));
            if (!k) d[v]=0;
            lb[c].w-=k;
            lb[c^1].w+=k;
            rest-=k;
            if (!rest) break;
        }
    }
    return flow-rest;
}
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
int n,m;
bool in (int x,int y) { return (x> 0)&&(y> 0)&&(x<=n)&&(y<=m); }
int bh (int x,int y) { return (x-1)*m+y; }
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    memset (top,-1,sizeof (top));
    sc(n),sc(m);
    s=n*m+1,t=s+1;
    int ans=0;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            int sb; sc(sb); ans+=sb;
            ((i+j)&1)?add (s,bh (i,j),sb):add (bh(i,j),t,sb);
            if ((i+j)&1)
                for (int d=0; d< 4; d++)
                    if (in (i+dx[d],j+dy[d])) add (bh (i,j),bh (i+dx[d],j+dy[d]),oo/10);
        }
    int flow;
    while ((bfs ()))
        while ((flow=dinic (s,oo))) ans-=flow;
    pr(ans);
    return 0;
}