#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 30;

int h,w;
bool maze[30][30][4];

struct state{
	int x;
	int y;
	int cost;
	bool operator <(const state& a)const{ return cost < a.cost; }
	bool operator >(const state& a)const{ return cost > a.cost; }
};

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int bfs(int sx,int sy){
	bool visited[30][30];
	rep(i,w)rep(j,h) visited[i][j]=false;
	state init;
	init.x=sx;init.y=sy;init.cost=0;
	visited[sx][sy]=true;
	queue<state> q;
	q.push(init);

	while(!q.empty()){
		state cur=q.front();q.pop();
		if(cur.x==w-1 && cur.y==h-1)
			return cur.cost;

		//cout << cur.x << " " << cur.y << " " << cur.cost<< endl;

		rep(i,4){
			state next;
			next=cur;
			next.x+=dx[i];
			next.y+=dy[i];
			next.cost++;
		
			if(0<=next.x&&next.x<w && 0<=next.y && next.y<h && maze[cur.x][cur.y][i]){
				if(!visited[next.x][next.y]){
					visited[next.x][next.y]=true;
					q.push(next);
				}
			}

		}
	}

	//cout << "here ?" << endl;
	return inf;
}

int dijkstra(void){
	int dp[30][30];
	rep(i,w)rep(j,h) dp[i][j]=inf;
	dp[w-1][h-1]=0;
	state init;
	init.x=w-1;init.y=h-1;init.cost=0;
	priority_queue< state,vector<state>, greater<state> > q;
	q.push(init);
	while(!q.empty()){
		state cur=q.top(); q.pop();
		if(cur.cost > dp[cur.x][cur.y])
			continue;
		
		if(cur.x==0 && cur.y==0)
			return cur.cost;

		rep(i,4){
		//	cout << cur.x << " " << cur.y  << " " << i << endl;
			state next=cur;
			next.x+=dx[i];
			next.y+=dy[i];

			if(0<=next.x&&next.x<w && 0<=next.y && next.y<h && maze[cur.x][cur.y][i]){
				maze[cur.x][cur.y][i]=false;
				maze[next.x][next.y][(i+2)%4]=false;
			
				next.cost=max(cur.cost+1,bfs(next.x,next.y));
				
				if(next.cost < dp[next.x][next.y]){
					dp[next.x][next.y]=next.cost;
					q.push(next);
				}

				maze[cur.x][cur.y][i]=true;
				maze[next.x][next.y][(i+2)%4]=true;
			}
		}
	}
	return inf;
}
int main(void){
	
	while(cin >> h >> w,h|w){
		rep(i,2*h-1){
			if(i&1){
				rep(j,w){  //ud
					int tmp;	
					cin >> tmp;
					tmp=1-tmp;
					maze[j][i/2][1]=tmp;
					maze[j][i/2+1][3]=tmp;
				}
			}else{
				rep(j,w-1){ //lr
					int tmp;
					cin >> tmp;
					tmp=1-tmp;
					maze[j][i/2][0]=tmp;
					maze[j+1][i/2][2]=tmp;
				}
			}
		}
		int ans=dijkstra();
		if(ans==inf)
			cout << -1 << endl;
		else
			cout << ans << endl;
	
	}
	return 0;
}

Measured memory_bytes: 1228