#include "bits/stdc++.h"
#include<unordered_map>
#pragma warning(disable:4996)
using namespace std;

const int My_Inf=2147483647;
const long long int My_LInf=9223372036854775807;


int H, W;
struct aa {
	int x;
	int y;
	int time;
};
class Compare {
public:
	//aaが昇順に並ぶ
	bool operator()(const aa&l, const aa&r) {
		return l.time> r.time;
	}
};
int memo[32][32][2][32][32];
int normalcheck(const int sx,const int sy,const vector<vector<int>>&tatedoors,const vector<vector<int>>&yokodoors, const bool tclose,const int closex, const int closey) {
	//if (memo[sx][sy][tclose][closex][closey] >= 0)return memo[sx][sy][tclose][closex][closey];
	vector<vector<int>>times(H, vector<int>(W, 99999));
	times[sy][sx] = 0;
	priority_queue<aa, vector<aa>, Compare>que;
	que.push(aa{ sx,sy,0 });
	while (!que.empty()) {
		aa atop(que.top());
		que.pop();
		const int nx = atop.x;
		const int ny = atop.y;
		if (nx == W-1&&ny == H - 1)return memo[sx][sy][tclose][closex][closey]=atop.time;

		if (yokodoors[ny][nx]) {
			if (times[ny - 1][nx]  > atop.time + 1) {
				times[ny - 1][nx] = atop.time + 1;
				que.push(aa{ nx,ny - 1,atop.time + 1 });
			}
		}
		if (yokodoors[ny+1][nx]) {
			if (times[ny + 1][nx]  > atop.time + 1) {
				times[ny + 1][nx] = atop.time + 1;
				que.push(aa{ nx,ny + 1,atop.time + 1 });
			}
		}
		if (tatedoors[ny][nx]) {
			if (times[ny ][nx - 1]  > atop.time + 1) {
				times[ny ][nx - 1] = atop.time + 1;
				que.push(aa{ nx - 1,ny,atop.time + 1 });
			}
		}
		if (tatedoors[ny][nx+1]) {
			if (times[ny][nx + 1]  > atop.time + 1) {
				times[ny][nx + 1] = atop.time + 1;
				que.push(aa{ nx + 1,ny,atop.time + 1 });
			}
		}
	}
	return memo[sx][sy][tclose][closex][closey]= 99999999;
}
bool check(const int needtime, vector<vector<int>>tatedoors, vector<vector<int>>yokodoors) {
	vector<vector<int>>times(H, vector<int>(W, 99999));
	times[0][0] = 0;
	priority_queue<aa, vector<aa>, Compare>que;
	que.push(aa{ 0,0,0 });
	while (!que.empty()) {
		aa atop(que.top());
		que.pop();
		const int nx = atop.x;
		const int ny = atop.y;
		if (nx == W - 1 &&ny == H - 1)return true;

		if (yokodoors[ny][nx]) {
			if (times[ny - 1][nx]  > atop.time + 1) {
				int closetime;
				{
					yokodoors[ny][nx] = false;
					closetime=normalcheck(nx, ny, tatedoors, yokodoors,false,nx,ny);
					yokodoors[ny][nx] = true;
				}
				if (atop.time + closetime <= needtime) {
					times[ny - 1][nx] = atop.time + 1;
					que.push(aa{ nx,ny - 1,atop.time + 1 });
				}
			}
		}
		if (yokodoors[ny + 1][nx]) {
			if (times[ny + 1][nx]  > atop.time + 1) {
				int closetime;
				{
					yokodoors[ny + 1][nx] = false;
					closetime = normalcheck(nx, ny, tatedoors, yokodoors,false,nx, ny + 1);
					yokodoors[ny + 1][nx] = true;
				}
				if (atop.time + closetime <= needtime) {
					times[ny+ 1][nx] = atop.time + 1;
					que.push(aa{ nx,ny + 1,atop.time + 1 });
				}
			}
		}
		if (tatedoors[ny][nx]) {
			if (times[ny][nx - 1] > atop.time + 1) {
				int closetime;
				{
					tatedoors[ny][nx] = false;
					closetime = normalcheck(nx, ny, tatedoors, yokodoors,true,nx,ny);
					tatedoors[ny][nx] = true;
				}
				if (atop.time + closetime <= needtime) {
					times[ny][nx - 1] = atop.time + 1;
					que.push(aa{ nx - 1,ny,atop.time + 1 });
				}
			}
		}
		if (tatedoors[ny][nx + 1]) {
			if (times[ny][nx + 1]  > atop.time + 1) {
				int closetime;
				{
					tatedoors[ny][nx+1] = false;
					closetime = normalcheck(nx, ny, tatedoors, yokodoors,true,nx+1,ny);
					tatedoors[ny][nx+1] = true;
				}
				if (atop.time + closetime <= needtime) {
					times[ny][nx + 1] = atop.time + 1;
					que.push(aa{ nx + 1,ny,atop.time + 1 });
				}
			}
		}
	}
	return false;
}
int main() { 
	while (1) {
		memset(memo, -1, sizeof(memo));

		cin >> H >> W;
		if (!H)break;
		vector<vector<int>>yokodoors;
		vector<vector<int>>tatedoors;
		yokodoors.resize(H+1);
		tatedoors.resize(H);
		for (int j = 0; j < W; ++j) {
			bool open = false;
			yokodoors[0].push_back(open);
			yokodoors[H].push_back(open);
		}

		for (int i = 0; i < 2 * H -1; ++i) {
			if (i % 2) {
				for (int j = 0; j < W; ++j) {
					bool open; cin >> open;
					open = !open;
					yokodoors[i / 2 + 1].push_back(open);
				}
			}
			else {
				tatedoors[i / 2].push_back(false);
				for (int j = 0; j < W - 1; ++j) {
					bool open; cin >> open;
					open = !open;
					tatedoors[i / 2].push_back(open);
				}
				tatedoors[i / 2].push_back(false);
			}
		}

		if (!check(1000000,tatedoors,yokodoors)) {
			cout << -1 << endl;
			continue;
		}
		else {
			int amin = 0;
			int amax = 1000;
			while (amin + 1 != amax) {
				int amid = (amin + amax) / 2;
				if (check(amid,tatedoors,yokodoors)) {
					amax = amid;

				}
				else {
					amin = amid;
				}
			}
			cout << amax << endl;
			continue;
		}
	}
	return 0;
}

Measured memory_bytes: 11300