#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair using namespace std; typedef long long ll; const int maxn=7e5+10; const ll inf=1e17; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,vis[maxn]; struct node { int x,y; }d[maxn]; int f[405][405]; ll d1[405][405],d2[405][405]; pi pre[405][405]; ll dis[405][405]; int tgr[405][405];//right int tgd[405][405];//down const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; struct nd { int x,y; nd(){} nd(int _x,int _y){x=_x,y=_y;} }; map<pair<pi,int>,int>mp; pair<pi,int> E[maxn]; int nct; int gid(int x,int y,int w){ if(!mp.count(m_p(m_p(x,y),w))){ E[nct+1]=m_p(m_p(x,y),w); return mp[m_p(m_p(x,y),w)]=++nct; }return mp[m_p(m_p(x,y),w)]; } bool operator<(nd a,nd b){ if(a.x!=b.x)return a.x<b.x; return a.y<b.y; } void Dijkstra(){ memset(dis,0x3f,sizeof(dis)); dis[0][0]=0; priority_queue<pair<ll,nd> >q; q.push(m_p(0,nd(0,0))); while(!q.empty()){ auto it=q.top().p2;q.pop(); int x=it.x,y=it.y; up(i,0,3){ int nx=x+dx[i],ny=y+dy[i]; if(nx<0||nx>n||ny<0||ny>m)continue; ll val=dis[x][y]; if(!i)val+=d1[x][y]; else if(i==1)val+=d1[x-1][y]; else if(i==2)val+=d2[x][y]; else val+=d2[x][y-1]; if(dis[nx][ny]>val){ dis[nx][ny]=val,pre[nx][ny]=m_p(x,y); //printf("pre[%d][%d]=%d,%d\n",nx,ny,pre[nx][ny].p1,pre[nx][ny].p2); q.push(m_p(-dis[nx][ny],nd(nx,ny))); } } } }vector<pi>g[maxn]; ll dis2[maxn]; void Dijkstra2(int u){ memset(dis2,0x3f,sizeof(dis2)); memset(vis,0,sizeof(vis)); dis2[u]=0; priority_queue<pair<ll,int> >q; q.push(m_p(0,u)); while(!q.empty()){ int x=q.top().p2;q.pop(); if(vis[x])continue;vis[x]=1; for(auto it:g[x]){ int y=it.p1,w=it.p2; if(dis2[y]>dis2[x]+w){ dis2[y]=dis2[x]+w; q.push(m_p(-dis2[y],y)); } } } } bool no(int a,int b,int c,int d){ if(a<0||b<0||c<0||d<0||a>n||b>m||c>n||d>m)return 1; if(a>c)swap(a,c),swap(b,d); if(a==c){ if(b>d)swap(b,d); return !tgr[a][b]; }return !tgd[a][b]; } bool nond(int x,int y){ if(x<0||y<0||x>n||y>m)return 1; return !f[x][y]; } void lk(int x,int y,int w){ //printf("(%d,%d,%d) (%d,%d,%d) %d\n",E[x].p1.p1,E[x].p1.p2,E[x].p2,E[y].p1.p1,E[y].p1.p2,E[y].p2,w); g[x].p_b(m_p(y,w)); } void slv(){ n=read(),m=read(); up(i,1,n){ up(j,1,m){ int x=read(); if(x)f[i][j]=1; } }up(i,0,n-1)up(j,0,m)d1[i][j]=read(); up(i,0,n)up(j,0,m-1)d2[i][j]=read(); Dijkstra(); up(i,1,n){ up(j,1,m)if(f[i][j]){ int x=i-1,y=j-1; while(x||y){ //cout<<"! "<<x<<" "<<y<<endl; auto it=pre[x][y]; if(it.p1==x){ if(tgr[x][min(it.p2,y)])break; tgr[x][min(it.p2,y)]=1; }else { if(tgd[min(x,it.p1)][it.p2])break; tgd[min(x,it.p1)][it.p2]=1; }x=it.p1,y=it.p2; } //cout<<"\n"; } } //cout<<"test "<<no(2,1,1,1)<<endl; //up(i,0,n)up(j,0,m)if(tgr[i][j])printf("tgr[%d][%d]=%d\n",i,j,tgr[i][j]); //up(i,0,n)up(j,0,m)if(tgd[i][j])printf("tgd[%d][%d]=%d\n",i,j,tgd[i][j]); up(i,0,n)up(j,0,m){ //cout<<"! "<<i<<" "<<j<<endl; if(no(i,j,i,j+1)&&nond(i+1,j+1)&&nond(i,j+1))lk(gid(i,j,0),gid(i,j,1),0); if(no(i,j,i+1,j)&&nond(i+1,j)&&nond(i+1,j+1))lk(gid(i,j,1),gid(i,j,2),0); if(no(i,j,i,j-1)&&nond(i,j)&&nond(i+1,j))lk(gid(i,j,2),gid(i,j,3),0); if(no(i,j,i-1,j)&&nond(i,j+1)&&nond(i,j))lk(gid(i,j,3),gid(i,j,0),0); } up(i,0,n)up(j,0,m){ if(nond(i,j+1)){ if(j+1<=m)lk(gid(i,j,0),gid(i,j+1,3),d2[i][j]); } if(nond(i+1,j+1)){ if(i+1<=n)lk(gid(i,j,1),gid(i+1,j,0),d1[i][j]); } if(nond(i+1,j)){ if(j-1>=0)lk(gid(i,j,2),gid(i,j-1,1),d2[i][j-1]); } if(nond(i,j)){ if(i-1>=0)lk(gid(i,j,3),gid(i-1,j,2),d1[i-1][j]); } } Dijkstra2(gid(0,0,3)); cout<<dis2[gid(0,0,2)]; }int main(){ //freopen("nue.in","r",stdin); //freopen("nue.out","w",stdout); slv(); fclose(stdin); fclose(stdout); //cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; } //1,0,1,10,253,11968