#include<bits/stdc++.h> using namespace std; #define int long long int n,m,c; int w[160030]; int id[410][410]; inline int trs(int x,int y){ return (x-1)*m+y; } struct edge{int v,c,w;}; vector<edge>g[160030]; mt19937 RD(time(0)); #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second inline void adde(int u,int v,int c,int w){ g[u].push_back({v,c,w}); g[v].push_back({u,c,w}); } int d[2710][1<<10]; inline void dij(){ memset(d,0x3f,sizeof(d)); int S=trs(1,1); d[S][0]=0; priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>q; q.push({0,{S,0}}); while(!q.empty()){ int w=p1(q.top()),u=p1(p2(q.top())),S=p2(p2(q.top())); q.pop(); if(d[u][S]<w)continue; // if(u==9&&S==0)cout<<u<<" "<<S<<" "<<w<<endl; for(edge e:g[u]){ int v=e.v,c=e.c,nw=e.w; int vS=S^nw; if(d[v][vS]>w+c){ d[v][vS]=w+c; q.push({w+c,{v,vS}}); } } } } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // freopen("nue.in","r",stdin); // freopen("nue.out","w",stdout); // system("grep VmPeak /proc/$PPID/status"); 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; } int P=(1<<10)-1; for(int i=1;i<c;i++){ if(c<=10)w[i]=1<<(i-1); else w[i]=RD()&((1<<10)-1); P^=w[i]; } w[c]=P; for(int i=1;i<n;i++) for(int j=1;j<=m;j++){ int x; cin>>x; int c=0; for(int k=1;k<j;k++) c|=w[id[i][k]]; // if(!c)cout<<trs(i,j)<<" "<<trs(i+1,j)<<endl; adde(trs(i,j),trs(i+1,j),x,c); } for(int i=1;i<=n;i++) for(int j=1;j<m;j++){ int x; cin>>x; adde(trs(i,j),trs(i,j+1),x,0); } dij(); cout<<d[trs(1,1)][(1<<10)-1]<<endl; cout.flush(); return 0; }