建图一时爽，找bug火葬厂…
题意其实就是求一个图的最小割，最小割等于最大流，但是这题点和边都很多，最大流可能会超时，我们就可以转化为对偶图的最短路问题，也就是面看成点，点看成面这样子，经过麻烦的建图之后，跑一下dijk最短路就好了

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=4000005;
const int M=8000005;
const int INF=0x3f3f3f3f;
int n,m,en;
struct Edge{
   
    int v,w,next;
}edge[M];
int cnt,head[N];
void init(){
   
    cnt=0;
    memset(head,-1,sizeof(head));
}
void addEdge(int u,int v,int w){
   
    edge[cnt]=Edge{
   v,w,head[u]};
    head[u]=cnt++;
    edge[cnt]=Edge{
   u,w,head[v]};
    head[v]=cnt++;
}
int dis[N];
bool vis[N];
struct node{
   
    int v,w;
    bool operator <(node a)const{
   
        return w>a.w;
    }
}tmp;
int Dijkstra(int s,int t){
   
    for(int i=0;i<=en;i++){
   
        dis[i]=INF;
        vis[i]=false;
    }
    dis[s]=0;
    priority_queue<node> q;
    q.push(node{
   s,0});
    while(!q.empty()){
   
        //printf("Fd\n");
        tmp=q.top();
        q.pop();
        int u=tmp.v;
        vis[u]=true;
        for(int i=head[u];i!=-1;i=edge[i].next){
   
            int v=edge[i].v;
            int w=edge[i].w;
            //printf("%d %d %d\n",u,v,w);
            if(!vis[v] && dis[v]>dis[u]+w){
   
                dis[v]=dis[u]+w;
                q.push(node{
   v,dis[v]});
            }
        }
    }
    return dis[t];
}
inline int number(int x,int y,bool up)//每个方格以左上角坐标表示
{
   
    int ret = ((m-1)*(x-1)+y-1)*2+1;
    if(up) ret++;
    return ret; // S:0 T:1
}
int main(void){
   
    //freopen("data.txt","r",stdin);
    scanf("%d%d",&n,&m);
    en=2*(n-1)*(m-1)+1;
    int t;
    //特判
    if(n==1 && m==1){
   
        printf("0\n");
    }else if(n==1){
   
        int ans=INF;
        for(int i=1;i<m;i++){
   
            scanf("%d",&t);
            ans=min(ans,t);
        }
        printf("%d\n",ans);
    }else if(m==1){
   
        int ans=INF;
        for(int i=1;i<n;i++){
   
            scanf("%d",&t);
            ans=min(ans,t);
        }
        printf("%d\n",ans);
    }else{
   
        init();
        //横边
        for(int i=1;i<=n;i++){
   
            for(int j=1;j<=m-1;j++){
   
                scanf("%d",&t);
                if(i==1){
   
                    //最上面一条直线的边，转化为第一层偶数平面和最上面平面end的边
                    addEdge(2*j,en,t);
                }else if(i==n){
   
                    //最下面一条直线的边，转化为最后一层平面和最下面平面0的边
                    //i就是当前层数，减去2就是第一层还有最后一层，中间的层数乘以每层有2(m-1)个平面
                    //再加2*j-1就是当前最后一层平面的编号，连上0
                    addEdge(0,(i-2)*2*(m-1)+2*j-1,t);
                }else{
   
                    //中间的边连上面一层的下平面和下面一层的上平面
                    addEdge(2*(m-1)*(i-1)+2*j,2*(i-2)*(m-1)+2*j-1,t);
                }
            }
        }
        //竖边，类似的处理方式
        for(int i=1;i<=n-1;i++){
   
            for(int j=1;j<=m;j++){
   
                scanf("%d",&t);
                if(j==1){
   
                    addEdge(0,(i-1)*(m-1)*2+1,t);
                }else if(j==m){
   
                    //printf("%d %d\n",i*(m-1)*2,number(i,j-1,true));
                    addEdge(i*(m-1)*2,en,t);
                }else{
   
                    addEdge((i-1)*(m-1)*2+(j-1)*2,(i-1)*(m-1)*2+2*j-1,t);
                }
            }
        }
        //斜边
        for(int i=1;i<=n-1;i++){
   
            for(int j=1;j<=m-1;j++){
   
                scanf("%d",&t);
                //printf("%d %d\n",(i-1)*2*(m-1)+2*(j-1)+1,(i-1)*2*(m-1)+2*j);
                addEdge((i-1)*2*(m-1)+2*(j-1)+1,(i-1)*2*(m-1)+2*j,t);
            }
        }
        // for(int i=0;i<=en;i++){
   
        // for(int j=head[i];j!=-1;j=edge[j].next){
   
        // int v=edge[j].v;
        // int w=edge[j].w;
        // printf("%d %d %d\n",i,v,w);
        // }
        // }
        int ans=Dijkstra(0,en);
        printf("%d\n",ans);
    }
    return 0;
}