#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second int n,m,c; int id[410][410]; inline int trs(int x,int y){ return (x-1)*m+y; } vector<pii>g[1600300]; inline void add(int u,int v,int c){ g[u].push_back({v,c}); g[v].push_back({u,c}); } inline void add_dir(int u,int v,int c){ g[u].push_back({v,c}); } inline int trs(int x,int y,int p){ return 4*((x-1)*m+y-1)+p+1; } int d[1000300]; inline void dij(int S){ memset(d,0x3f,sizeof(d)); d[S]=0; priority_queue<pii,vector<pii>,greater<pii>>q; q.push({0,S}); while(!q.empty()){ int w=p1(q.top()),u=p2(q.top()); q.pop(); if(d[u]<w)continue; for(pii e:g[u]){ int v=p1(e),c=p2(e); if(d[v]>w+c){ d[v]=w+c; q.push({w+c,v}); } } } } int dn[410][410],rt[410][410]; bool vd[410][410],vr[410][410]; bool vis[1000300]; inline void mk(int u,int v){ int ux=(u-1)/m+1,uy=(u-1)%m+1; int vx=(v-1)/m+1,vy=(v-1)%m+1; if(ux>vx||uy>vy)swap(ux,vx),swap(uy,vy); if(ux!=vx)vd[ux][uy]=1; else vr[ux][uy]=1; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); freopen("genshin.in","r",stdin); freopen("genshin.out","w",stdout); cin>>n>>m; n++,m++; for(int i=1;i<n;i++) for(int j=1;j<m;j++){ bool x; cin>>x; if(x){ id[i][j]=++c; vr[i][j]=vd[i][j]=vd[i][j+1]=vr[i+1][j]=1; } } for(int i=1;i<n;i++) for(int j=1;j<=m;j++) cin>>dn[i][j],add(trs(i,j),trs(i+1,j),dn[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<m;j++) cin>>rt[i][j],add(trs(i,j),trs(i,j+1),rt[i][j]); dij(trs(1,1)); vd[0][1]=1; queue<int>q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(id[i][j])q.push(trs(i,j)),vis[trs(i,j)]=1; while(!q.empty()){ int u=q.front(); q.pop(); for(pii e:g[u]){ int v=p1(e),c=p2(e); // cout<<u<<" "<<v<<" "<<c<<" "<<d[v]<<endl; if(d[v]+c==d[u]){ mk(u,v); if(!vis[v])vis[v]=1,q.push(v); } } } for(int i=1;i<=n*m;i++)g[i].clear(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(!vr[i][j-1])add_dir(trs(i,j,0),trs(i,j,1),0); if(!vd[i][j])add_dir(trs(i,j,1),trs(i,j,2),0); if(!vr[i][j])add_dir(trs(i,j,2),trs(i,j,3),0); if(!vd[i-1][j])add_dir(trs(i,j,3),trs(i,j,0),0); } for(int i=1;i<=n;i++) for(int j=1;j<m;j++) add(trs(i,j,3),trs(i,j+1,0),rt[i][j]), add(trs(i,j,2),trs(i,j+1,1),rt[i][j]); for(int i=1;i<n;i++) for(int j=1;j<=m;j++) add(trs(i,j,1),trs(i+1,j,0),dn[i][j]), add(trs(i,j,2),trs(i+1,j,3),dn[i][j]); dij(trs(1,1,0)); cout<<d[trs(1,1,3)]<<endl; // for(int u=1;u<=trs(n,m,3);u++) // for(pii e:g[u]) // cout<<u<<" "<<p1(e)<<" "<<p2(e)<<endl; cout.flush(); return 0; }