1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 #define N 1100000 6 int n,m,first[N],next[N*6],v[N*6],w[N*6],tot,jy,ans,vis[N],S,T,xx,pos[N]; 7  8 void Add(int x,int y,int z) 9 {10     w[tot] = z;11     v[tot] = y;12     next[tot] = first[x];13     first[x] = tot++;14 }15 16 void add(int x,int y,int z)17 {18     Add(x,y,z);19     Add(y,x,z);20 }21 22 bool bfs()23 {24     memset(vis,-1,sizeof(vis)),vis[S]=0;25     queue<int>q;26     q.push(S);27     while(!q.empty())28     {29         int t=q.front();30         q.pop();31         for(int i=first[t]; ~i; i=next[i])32             if(w[i]&&vis[v[i]]==-1)33                 vis[v[i]]=vis[t]+1,q.push(v[i]);34     }35     return vis[T]!=-1;36 }37 38 int dfs(int x,int y)39 {40     if(x==T)return y;41     int r=0;42     for(int i=first[x]; ~i&&y>r; i=next[i])43         if(w[i]&&vis[v[i]]==vis[x]+1)44         {45             int t=dfs(v[i],min(y-r,w[i]));46             w[i]-=t,w[i^1]+=t,r+=t;47         }48     if(!r)vis[x]=-1;49     return r;50 }51 52 int main()53 {54     memset(first,-1,sizeof(first));55     scanf("%d%d",&n,&m);56     S=m+1,T=n*m+m;57     for(int i=1; i<=n; i++)58         for(int j=1; j<m; j++)59             scanf("%d",&xx),add(i*m+j,i*m+j+1,xx);60     for(int i=1; i<n; i++)61         for(int j=1; j<=m; j++)62             scanf("%d",&xx),add(i*m+j,(i+1)*m+j,xx);63     for(int i=1; i<n; i++)64         for(int j=1; j<m; j++)65             scanf("%d",&xx),add(i*m+j,(i+1)*m+j+1,xx);66 67     while(bfs())68         while(jy=dfs(S,0x3fffffff))69             ans+=jy;70     printf("%d\n",ans);71 }