#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define INF 1000000000

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

int main()
{
	while(1){
      int h, w;
      cin>>h>>w;
      if(h==0 && w==0) break;
      int yk[30][30], tt[30][30];
      for(int i=0; i<h; i++){
        for(int j=0; j<w-1; j++){
          cin>>yk[i][j];
        }
        if(i==h-1) break;
        for(int j=0; j<w; j++){
          cin>>tt[i][j];
        }
      }
      int d[2][30][30][30][30];
      for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
			for(int k=0; k<h; k++){
				for(int l=0; l<w-1; l++){
					d[0][k][l][i][j]=INF;
				}
			}
			for(int k=0; k<h-1; k++){
				for(int l=0; l<w; l++){
					d[1][k][l][i][j]=INF;
				}
			}
		}
      }
	  for(int k=0; k<h; k++){
		  for(int l=0; l<w-1; l++){
			  if(yk[k][l]==1) continue;
			  d[0][k][l][h-1][w-1]=0;
			  queue<P> que;
			  que.push(P(h-1, w-1));
			  while(!que.empty()){
				P p=que.front();
				que.pop();
				int x=p.first;
				int y=p.second;
				if(x-1>=0){
					if(tt[x-1][y]==0 && d[0][k][l][x-1][y]>d[0][k][l][x][y]+1){
						d[0][k][l][x-1][y]=d[0][k][l][x][y]+1;
						que.push(P(x-1, y));
					}
				}
				if(x+1<h){
					if(tt[x][y]==0 && d[0][k][l][x+1][y]>d[0][k][l][x][y]+1){
						d[0][k][l][x+1][y]=d[0][k][l][x][y]+1;
						que.push(P(x+1, y));
					}
				}
				if(y-1>=0){
					if(yk[x][y-1]==0 && (!(x==k && y-1==l)) && d[0][k][l][x][y-1]>d[0][k][l][x][y]+1){
						d[0][k][l][x][y-1]=d[0][k][l][x][y]+1;
						que.push(P(x, y-1));
					}
				}
				if(y+1<w){
					if(yk[x][y]==0 && (!(x==k && y==l)) && d[0][k][l][x][y+1]>d[0][k][l][x][y]+1){
						d[0][k][l][x][y+1]=d[0][k][l][x][y]+1;
						que.push(P(x, y+1));
					}
				}
			  }
		  }
      }
	  for(int k=0; k<h-1; k++){
		  for(int l=0; l<w; l++){
			  if(tt[k][l]==1) continue;
			  d[1][k][l][h-1][w-1]=0;
			  queue<P> que;
			  que.push(P(h-1, w-1));
			  while(!que.empty()){
				P p=que.front();
				que.pop();
				int x=p.first;
				int y=p.second;
				if(x-1>=0){
					if(tt[x-1][y]==0 && (!(x-1==k && y==l)) && d[1][k][l][x-1][y]>d[1][k][l][x][y]+1){
						d[1][k][l][x-1][y]=d[1][k][l][x][y]+1;
						que.push(P(x-1, y));
					}
				}
				if(x+1<h){
					if(tt[x][y]==0 && (!(x==k && y==l)) && d[1][k][l][x+1][y]>d[1][k][l][x][y]+1){
						d[1][k][l][x+1][y]=d[1][k][l][x][y]+1;
						que.push(P(x+1, y));
					}
				}
				if(y-1>=0){
					if(yk[x][y-1]==0 && d[1][k][l][x][y-1]>d[1][k][l][x][y]+1){
						d[1][k][l][x][y-1]=d[1][k][l][x][y]+1;
						que.push(P(x, y-1));
					}
				}
				if(y+1<w){
					if(yk[x][y]==0 && d[1][k][l][x][y+1]>d[1][k][l][x][y]+1){
						d[1][k][l][x][y+1]=d[1][k][l][x][y]+1;
						que.push(P(x, y+1));
					}
				}
			  }
		  }
      }
	  bool no=0;
	  for(int k=0; k<h; k++){
		  for(int l=0; l<w-1; l++){
			  if(yk[k][l]==0 && d[0][k][l][0][0]==INF){
				  no=1;
				  break;
			  }
		  }
		  if(no) break;
	  }
	  if(no){
		  cout<<-1<<endl;
		  continue;
	  }
	  for(int k=0; k<h-1; k++){
		  for(int l=0; l<w; l++){
			  if(tt[k][l]==0 && d[1][k][l][0][0]==INF){
				  no=1;
				  break;
			  }
		  }
		  if(no) break;
	  }
	  if(no){
		  cout<<-1<<endl;
		  continue;
	  }
      priority_queue<Pint, vector<Pint>, greater<Pint> > que2;
      int d2[30][30];
      for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
          d2[i][j]=INF;
        }
      }
      d2[h-1][w-1]=0;
      que2.push(Pint(0, P(h-1, w-1)));
      while(!que2.empty()){
        Pint p=que2.top();
        que2.pop();
        int x=p.second.first, y=p.second.second;
        if(d2[x][y]<p.first) continue;
		if(y-1>=0){
			if(yk[x][y-1]==0 && d2[x][y-1]>max(d2[x][y]+1, d[0][x][y-1][x][y-1])){
				d2[x][y-1]=max(d2[x][y]+1, d[0][x][y-1][x][y-1]);
				que2.push(Pint(d2[x][y-1], P(x, y-1)));
			}
		}
		if(y+1<w){
			if(yk[x][y]==0 && d2[x][y+1]>max(d2[x][y]+1, d[0][x][y][x][y+1])){
				d2[x][y+1]=max(d2[x][y]+1, d[0][x][y][x][y+1]);
				que2.push(Pint(d2[x][y+1], P(x, y+1)));
			}
		}
		if(x-1>=0){
			if(tt[x-1][y]==0 && d2[x-1][y]>max(d2[x][y]+1, d[1][x-1][y][x-1][y])){
				d2[x-1][y]=max(d2[x][y]+1, d[1][x-1][y][x-1][y]);
				que2.push(Pint(d2[x-1][y], P(x-1, y)));
			}
		}
		if(x+1<h){
			if(tt[x][y]==0 && d2[x+1][y]>max(d2[x][y]+1, d[1][x][y][x+1][y])){
				d2[x+1][y]=max(d2[x][y]+1, d[1][x][y][x+1][y]);
				que2.push(Pint(d2[x+1][y], P(x+1, y)));
			}
		}
	  }
	  cout<<d2[0][0]<<endl;
	}
	return 0;
}


Measured memory_bytes: 9364