import core.stdc.stdio;
import std.traits;
import std.algorithm;
import std.typecons;
import std.stdio;

int[][] wall;
bool[][][] pass;
int[][][][] dist;
int[][][] buf;

int[] dx=[0,-1,0,1];
int[] dy=[-1,0,1,0];

static immutable int inf=114514;
int w,h;

void Clear(T,U)(ref T t,U u){
	static if(isArray!T)
		foreach(ref d;t)
			d.Clear(u);
	else
		t=u;
}

void SetPass(){
	pass.Clear(false);
	foreach(i;0..h)
		foreach(j;0..w){
			if(i>0)
				pass[i][j][0]=wall[i*2-1][j]==0;
			if(j>0)
				pass[i][j][1]=wall[i*2][j-1]==0;
			if(i<h-1)
				pass[i][j][2]=wall[i*2+1][j]==0;
			if(j<w-1)
				pass[i][j][3]=wall[i*2][j]==0;
		}
}

bool inside(int x,int y){
	return 0<=x&&x<w&&0<=y&&y<h;
}

int[] qx,qy,qd;
void BFS(int[][] dst){
	SetPass;
	dst.Clear(inf);
	qx[0]=w-1;
	qy[0]=h-1;
	qd[0]=0;
	dst[h-1][w-1]=0;
	int q=1;
	int i=0;
	while(i<q){
		int x=qx[i],y=qy[i],d=qd[i];
		i++;
		foreach(k;0..4){
			int nx=x+dx[k],ny=y+dy[k];
			if(pass[y][x][k]&&inside(nx,ny)&&dst[ny][nx]==inf){
				qx[q]=nx;
				qy[q]=ny;
				qd[q++]=d+1;
				dst[ny][nx]=d+1;
			}
		}
	}
}

bool Solve(){
	scanf("%d%d",&h,&w);
	if(w==0&&h==0)
		return false;
	foreach(i;0..2*h-1)
		foreach(j;0..w-1+(i&1))
			scanf("%d",&wall[i][j]);
	BFS(dist[0][0]);
	if(dist[0][0][0][0]==inf){
		printf("-1\n");
		return true;
	}
	foreach(i;0..2*h-1)
		foreach(j;0..w-1+(i&1))
			if(wall[i][j]==0){
				wall[i][j]=1;
				BFS(dist[i][j]);
				wall[i][j]=0;
				if(dist[i][j][0][0]==inf){
					printf("-1\n");
					return true;
				}
			}
	int[][] now=buf[0];
	now.Clear(inf);
	int[][] next=buf[1];
	int ans=inf;
	now[0][0]=0;
	foreach(k;0..h*w){
		next.Clear(inf);
		foreach(i;0..h)
			foreach(j;0..w){
				if(pass[i][j][0])
					next[i][j]=min(next[i][j],max(now[i-1][j],dist[i*2-1][j][i-1][j]+k));
				if(pass[i][j][1])
					next[i][j]=min(next[i][j],max(now[i][j-1],dist[i*2][j-1][i][j-1]+k));
				if(pass[i][j][2])
					next[i][j]=min(next[i][j],max(now[i+1][j],dist[i*2+1][j][i+1][j]+k));
				if(pass[i][j][3])
					next[i][j]=min(next[i][j],max(now[i][j+1],dist[i*2][j][i][j+1]+k));
			}
		swap(now,next);
		ans=min(ans,max(k+1,now[h-1][w-1]));
	}
	printf("%d\n",ans);
	return true;
}

void main(){
	wall=new int[][](60,30);
	pass=new bool[][][](30,30,4);
	dist=new int[][][][](60,30,30,30);
	buf=new int[][][](2,30,30);
	qx=new int[1000];
	qy=new int[1000];
	qd=new int[1000];
	while(Solve){}
}