#include<bits/stdc++.h>
#define reps(i,a,b) for(int i=(a); i<(b); ++i)
#define rep(i,n) reps(i,0,n)
#define X first
#define Y second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

struct UnionFind{
	std::vector<int> data;
	UnionFind(int size): data(size, -1) {}

	bool unite(int x, int y){
		x=root(x);
		y=root(y);
		if( x != y ){
			if( data[y] < data[x] ) std::swap(x, y);
			data[x] += data[y];
			data[y] = x;
		}
		return x!=y;
	}

	bool find(int x, int y){
		return root(x) == root(y);
	}

	int root(int x){
		return (data[x] < 0)? x : data[x]=root(data[x]);
	}

	int size(int x){
		return -data[ root(x) ];
	}
};

// R, U, L, D
const int vx[]={1,0,-1,0}, vy[]={0,1,0,-1};

const int INF = 1e9;

int h, w;
int ans;
map<pii,int> cost;
int tb[50][50];
void solve(map<pii,int> &mp, int x, int y, int d){
	queue<pair<pii,int>> que;
	que.push( {pii(x,y), d} );
	tb[x][y] = d;
	while(!que.empty()){
		auto cur = que.front().X;
		int x = cur.X;
		int y = cur.Y;
		int d = que.front().Y;
		que.pop();
		rep(k,4){
			int nx = x + vx[k];
			int ny = y + vy[k];
			if( nx < 0 || nx >= w || ny < 0 || ny >= h ) continue;
			if( mp[cur] & (1<<k) ) continue;
			if( tb[nx][ny] > d + 1 ){
				tb[nx][ny] = d + 1;
				que.push( {pii(nx,ny), d+1} );
			}
		}
	}
	//if( !tb.count(pii(w-1,h-1)) ) tb[pii(w-1,h-1)] = INF;
	cost[pii(x,y)] = max(cost[pii(x,y)], tb[w-1][h-1]);
}

int main(){
	ios_base::sync_with_stdio(0);
	while(cin >> h >> w, h|w){
		cost.clear();
		map<pii,int> mp;
		int d;
		rep(i,h-1){
			rep(j,w-1){
				cin >> d;
				if( d == 1 ){
					mp[pii(j,i)]   |= (1<<0);
					mp[pii(j+1,i)] |= (1<<2);
				}
			}
			rep(j,w){
				cin >> d;
				if( d == 1 ){
					mp[pii(j,i)]   |= (1<<1);
					mp[pii(j,i+1)] |= (1<<3);
				}
			}
		}
		int i = h-1;
		rep(j,w-1){
			cin >> d;
			if( d == 1 ){
				mp[pii(j,i)]   |= (1<<0);
				mp[pii(j+1,i)] |= (1<<2);
			}
		}
		rep(i,h) mp[pii(0,i)]   |= (1<<2);
		rep(i,h) mp[pii(w-1,i)] |= (1<<0);
		rep(i,w) mp[pii(i,0)]   |= (1<<3);
		rep(i,w) mp[pii(i,h-1)] |= (1<<1);

		fill( tb[0], tb[0]+50*50, INF );
		map<pii,int> tb_s;
		solve(mp, 0, 0, 0);
		rep(y,h) rep(x,w) tb_s[pii(x,y)] = tb[x][y];
		ans = 0;
//		rep(i,h){
//			rep(j,w) cout << tb_s[pii(j,i)] << " ";
//			cout << endl;
//		}

		auto mp1 = mp;
		rep(y,h) rep(x,w) rep(k,4){
			if( mp[pii(x,y)] & (1<<k) ) continue;
			if( cost[pii(x,y)] >= INF ) continue;
			int nx = x + vx[k];
			int ny = y + vy[k];
			mp1[pii(x,y)]   |= (1<<k);
			mp1[pii(nx,ny)] |= (1<<((k+2)%4));
			fill( tb[0], tb[0]+50*50, INF );
			//solve(mp1, tb, x, y, tb_s[pii(x,y)]);
			solve(mp1, x, y, 0);
			mp1[pii(x,y)]   ^= (1<<k);
			mp1[pii(nx,ny)] ^= (1<<((k+2)%4));
			//cout << "solve: " << x << " " << y << " k=" << k << endl;
			//rep(i,h){
			//	rep(j,w) cout << tb[pii(j,i)] << " ";
			//	cout << endl;
			//}
		}

//		cout << "cost:" << endl;
//		rep(i,h){
//			rep(j,w) cout << (cost[pii(j,i)]==INF ? 99 : cost[pii(j,i)]) << " ";
//			cout << endl;
//		}

		int l=0, r=1000;
		while(r-l>1){
			int limit = (l+r)/2;
			typedef pair<pii,pii> PII;
			priority_queue<PII, vector<PII>, greater<PII>> que;
			pii memo[50][50];
			fill( memo[0], memo[0]+50*50, pii(INF,INF) );
			que.push({{cost[pii(0,0)],0},pii(0,0)});
			while(!que.empty()){
				int c = que.top().X.X;
				int d = que.top().X.Y;
				int x = que.top().Y.X;
				int y = que.top().Y.Y;
				que.pop();
				if( memo[x][y] < pii(c,d) ) continue;
				//if( memo.count(pii(x,y)) ) continue;
				//if( c > limit ) continue;
				//memo[pii(x,y)] = pii(c,d);
				//ans = max(ans, c);
				if( pii(x,y) == pii(w-1,h-1) ) break;
				rep(k,4){
					int nx = x + vx[k];
					int ny = y + vy[k];
					int nc = d + 1 + cost[pii(nx,ny)];
					nc = min(nc, INF);
					if( nx < 0 || nx >= w || ny < 0 || ny >= h ) continue;
					if( mp[pii(x,y)] & (1<<k) ) continue;
					if( memo[nx][ny] > pii(nc,d+1) ){
						if( nc <= limit ){
							memo[nx][ny] = pii(nc, d+1);
							que.push( {pii(nc, d+1), pii(nx, ny)} );
						}
					}
				}
			}
			if( memo[w-1][h-1].X < INF ){
				r = limit;
			}else{
				l = limit;
			}
		}
		ans = (r<1000 ? r : -1);
//		pii pos = {w-1,h-1};
//		ans = max(ans, memo[pos].X);
//		while( pos != pii(0,0) ){
//			int x = pos.X;
//			int y = pos.Y;
//			rep(k,4){
//				int nx = x + vx[k];
//				int ny = y + vy[k];
//				int nc = d + 1 + cost[pii(nx,ny)];
//				if( nx < 0 || nx >= w || ny < 0 || ny >= h ) continue;
//				if( mp[pii(x,y)] & (1<<k) ) continue;
//				if( memo.count(pii(nx,ny)) && memo[pii(nx,ny)].Y < memo[pos].Y ){
//					pos = pii(nx,ny);
//					break;
//				}
//			}
//			ans = max(ans, memo[pos].X);
//		}

//		multimap<int, pii> order;
//		for(auto t: memo) order.insert({ t.Y.X, t.X });
//		UnionFind uf(1000);
//		for(auto t: order){
//			int x = t.Y.X;
//			int y = t.Y.Y;
//			rep(k,4){
//				int nx = x + vx[k];
//				int ny = y + vy[k];
//				if( nx < 0 || nx >= w || ny < 0 || ny >= h ) continue;
//				if( mp[pii(x,y)] & (1<<k) ) continue;
//				if( memo[pii(nx,ny)].X <= t.X ){
//					uf.unite( nx+ny*w, x+y*w );
//				}
//			}
////			cout << "order: " << x << " " << y << " " << t.X << endl;
//			if( uf.find(0, (w-1)+(h-1)*w ) ){
//				ans = t.X;
//				break;
//			}
//		}

		cout << (ans >= INF ? -1 : ans) << endl;
	}
	return 0;
}

Measured memory_bytes: 3376