高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。

第一行两个正整数n，m。接下来是六个矩阵第一个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。第二个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。第三个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。第四个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。第五个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。第六个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。

输出一个整数，表示喜悦值总和的最大值

  1 /*by SilverN*/  2 #include<algorithm>  3 #include<iostream>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #include<queue>  9 using namespace std; 10 const int mx[5]={0,1,0,-1,0}; 11 const int my[5]={0,0,1,0,-1}; 12 const int INF=1e9; 13 const int mxn=20010; 14 int read(){ 15     int x=0,f=1;char ch=getchar(); 16     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 17     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 18     return x*f; 19 } 20 struct edge{ 21     int v,nxt,f; 22 }e[mxn*50]; 23 int hd[mxn],mct=1; 24 void add_edge(int u,int v,int f){ 25     e[++mct].v=v;e[mct].nxt=hd[u];e[mct].f=f;hd[u]=mct;return; 26 } 27 void insert(int u,int v,int f){ 28     add_edge(u,v,f); 29     add_edge(v,u,0); 30     return; 31 } 32 int n,m,S,T; 33 int d[mxn]; 34 bool BFS(){ 35     memset(d,0,sizeof d); 36     queue<int>q; 37     d[S]=1; 38     q.push(S); 39     while(!q.empty()){ 40         int u=q.front();q.pop(); 41         for(int i=hd[u];i;i=e[i].nxt){ 42             int v=e[i].v; 43             if(e[i].f && !d[v]){ 44                 d[v]=d[u]+1; 45                 q.push(v); 46             } 47         } 48     } 49     return d[T]; 50 } 51 int DFS(int u,int lim){ 52     if(u==T)return lim; 53     int f=0,tmp; 54     for(int i=hd[u];i;i=e[i].nxt){ 55         int v=e[i].v; 56         if(d[v]==d[u]+1 && e[i].f && (tmp=DFS(v,min(lim,e[i].f)))){ 57             e[i].f-=tmp; 58             e[i^1].f+=tmp; 59             f+=tmp; 60             lim-=tmp; 61             if(!lim)return f; 62         } 63     } 64     d[u]=0; 65     return f; 66 } 67 int Dinic(){ 68     int res=0; 69     while(BFS())res+=DFS(S,INF); 70     return res; 71 } 72 int id[110][110],cnt=0,ed; 73 void init(){ 74     for(int i=1;i<=n;i++) 75      for(int j=1;j<=m;j++) 76          id[i][j]=++cnt; 77     ed=n*m; 78     return; 79 } 80 int ans=0; 81 int A[mxn],Si[mxn]; 82 void solve(){ 83     int i,j,x; 84     int smm=0; 85     for(i=1;i<=n;i++) 86         for(j=1;j<=m;j++){ 87             x=read(); 88             A[id[i][j]]=x*2,smm+=x; 89     } 90     for(i=1;i<=n;i++) 91         for(j=1;j<=m;j++){ 92             x=read(); 93             Si[id[i][j]]=x*2,smm+=x; 94     } 95     for(i=1;i<n;i++) 96         for(j=1;j<=m;j++){ 97             x=read();smm+=x; 98             add_edge(id[i][j],id[i+1][j],x); 99             add_edge(id[i+1][j],id[i][j],x);100             A[id[i][j]]+=x;101             A[id[i+1][j]]+=x;102         }103     for(i=1;i<n;i++)104         for(j=1;j<=m;j++){105             x=read();smm+=x;106             add_edge(id[i][j],id[i+1][j],x);107             add_edge(id[i+1][j],id[i][j],x);108             Si[id[i][j]]+=x;109             Si[id[i+1][j]]+=x;110         }111     for(i=1;i<=n;i++)112         for(j=1;j<m;j++){113             x=read();smm+=x;114             add_edge(id[i][j],id[i][j+1],x);115             add_edge(id[i][j+1],id[i][j],x);116             A[id[i][j]]+=x;117             A[id[i][j+1]]+=x;118         }119     for(i=1;i<=n;i++)120         for(j=1;j<m;j++){121             x=read();smm+=x;122             add_edge(id[i][j],id[i][j+1],x);123             add_edge(id[i][j+1],id[i][j],x);124             Si[id[i][j]]+=x;125             Si[id[i][j+1]]+=x;126         }127     for(i=1;i<=n;i++)128         for(j=1;j<=m;j++){129             insert(S,id[i][j],A[id[i][j]]);130             insert(id[i][j],T,Si[id[i][j]]);131         }132     ans=smm-Dinic()/2;133     return;134 }135 int main(){136     int i,j,x;137     n=read();m=read();138     S=0;T=n*m+1;139     init();140     solve();141     printf("%d\n",ans);142     return 0;143 }