#include<bits/stdc++.h> using namespace std; #define int long long #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w #define pii pair<int,int> #define fr first #define sc second #define mk make_pair int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=410,N=11,Mod=998244353,inf=1000000000000000000; int n,m,k,ans,a[MAXN][MAXN],w[5][MAXN][MAXN],d[5][MAXN][MAXN],mx[5]={1,0,-1,0},my[5]={0,-1,0,1}; struct Edge{int v,nx,w;}edge[MAXN*MAXN*5<<1];int h[MAXN*MAXN*5],CNT;void add_side(int u,int v,int w){ // cout<<u<<" "<<v<<" "<<w<<endl; edge[++CNT]={v,h[u],w};h[u]=CNT;} void init(){memset(h,0,sizeof(h));CNT=1;} priority_queue<pii>Q; int p1(int x,int y){return (x-1)*(m+1)+y;} int p2(int x,int y,int t){return t*(n+1)*(m+1)+(x-1)*(m+1)+y;} int vis[MAXN*MAXN*5],dis[MAXN*MAXN*5],pre[MAXN*MAXN*5]; void dji(int x){ memset(dis,0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); Q.push(mk(0,x)); dis[x]=0; while(!Q.empty()){ int u=Q.top().sc;Q.pop(); if(vis[u])continue; vis[u]=1; for(inx(u))if(dis[u]+w<dis[v]){ dis[v]=dis[u]+w,pre[v]=u; Q.push(mk(-dis[v],v)); } } } bool check(int s){ int x=(s-1)/(m+1)+1,y=(s-1)%(m+1)+1; if(!pre[s])return 1; s=pre[s]; int px=(s-1)/(m+1)+1,py=(s-1)%(m+1)+1; if(px==x) if(py==y+1)return d[3][x][y]; else return d[1][x][y]; else if(px==x+1)return d[0][x][y]; else return d[2][x][y]; } void prt(int s){ int x=(s-1)/(m+1)+1,y=(s-1)%(m+1)+1; if(!pre[s])return; s=pre[s]; int px=(s-1)/(m+1)+1,py=(s-1)%(m+1)+1; // cout<<x<<" "<<y<<" "<<px<<" "<<py<<endl; if(px==x) if(py==y+1)d[3][x][y]=d[1][px][py]=1; else d[1][x][y]=d[3][px][py]=1; else if(px==x+1)d[0][x][y]=d[2][px][py]=1; else d[2][x][y]=d[0][px][py]=1; } void slv(){ n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)a[i][j]=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m+1;j++)w[0][i][j]=w[2][i+1][j]=read(),add_side(p1(i,j),p1(i+1,j),w[0][i][j]),add_side(p1(i+1,j),p1(i,j),w[2][i+1][j]); for(int i=1;i<=n+1;i++) for(int j=1;j<=m;j++)w[3][i][j]=w[1][i][j+1]=read(),add_side(p1(i,j),p1(i,j+1),w[3][i][j]),add_side(p1(i,j+1),p1(i,j),w[1][i][j+1]); dji(p1(1,1)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)if(a[i][j]){ int now=p1(i,j); while(!check(now)){ prt(now); now=pre[now]; } } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)if(a[i][j])d[0][i][j]=d[3][i][j]=d[1][i][j+1]=d[0][i][j+1]=d[2][i+1][j]=d[3][i+1][j]=d[2][i+1][j+1]=d[1][i+1][j+1]=1; // for(int i=1;i<=4;i++) // for(int j=1;j<=4;j++) // for(int o=0;o<4;o++)cout<<i<<"_"<<j<<"_"<<o<<endl;; init(); for(int i=1;i<=n+1;i++){ for(int j=1;j<=m+1;j++){ for(int o=0;o<4;o++){ if(!d[o][i][j]){ // cout<<i<<"_"<<j<<"_"<<o<<" "<<i<<"_"<<j<<"_"<<(o+1)%4<<" "<<0<<endl; add_side(p2(i,j,o),p2(i,j,(o+1)%4),0); } int nx=i+mx[o],ny=j+my[o]; if(!nx||!ny||nx>n+1||ny>m+1)continue; // cout<<i<<"_"<<j<<"_"<<o<<" "<<nx<<"_"<<ny<<"_"<<(o+3)%4<<" "<<w[o][i][j]<<endl; add_side(p2(i,j,o),p2(nx,ny,(o+3)%4),w[o][i][j]); } } } dji(p2(1,1,3)); printf("%lld",dis[p2(1,1,1)]); } signed main(){ slv(); return 0; }