#include <map>
#include <queue>
#include <cstring>
#include <cstdio>
#include <vector>
#include <iostream>
using namespace std;
 
vector<string> line;

struct NODE{
    int id,cost,maximum;
    NODE(int id,int cost,int maximum) : id(id),cost(cost),maximum(maximum){}
};
 
bool operator < (const NODE &a,const NODE &b){
    return a.maximum > b.maximum;
}
 

int tmp[100][100];
int XX[1000],YY[1000];
int sz = 0;
int id(int x,int y){
	if( tmp[x][y] != -1 ) return tmp[x][y];
	XX[sz] = x;
	YY[sz] = y;
	return tmp[x][y] = sz++;
}

int X(int id){ return XX[id]; }
int Y(int id){ return YY[id]; }

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


int done[910][910]={};

int main(){
	memset(tmp,-1,sizeof(tmp));
    int H,W;
    while(cin >> H >> W && H){
        int s = id(0,0);
        int g = id(2*W-2,2*H-2);
         
        line = vector<string>(H*2-1);
        getline(cin,line[0]); //dummy
        for(int i = 0 ; i < H*2-1 ; i++){
            getline(cin,line[i]);
            if(!(i&1))line[i] += " ";
        }
         
        int dir[62][62][2];
        for(int i = 0 ; i < 62 ; i++)
            for(int j = 0 ; j < 62 ; j++)
                for(int k = 0 ; k < 2 ; k++)
                    dir[i][j][k] = 1e9;
     
        int maximum = 0;
        for(int y = 0 ; y < 2*H-1 ; y++){
            for(int x = 0 ; x < 2*W ; x++){
                if( line[y][x] != '0' ) continue;
                line[y][x] = '1';
                int c1,c2;
                if( y % 2 == 0 ){
                    c1 = id(x-1,y);
                    c2 = id(x+1,y);
                }else{
                    c1 = id(x,y-1);
                    c2 = id(x,y+1);
                }
                for(int k = 0 ; k < 2 ; k++){
                    // test
                    int tmp[2000];
                    memset(tmp,-1,sizeof(tmp));
                    queue<int> Q;
                    tmp[c1] = 0;
                    Q.push(c1);
                    while(Q.size()){
                        int q = Q.front(); Q.pop();
                        for(int i = 0 ; i < 4 ; i++){
                            int tx = X(q) + dx[i];
                            int ty = Y(q) + dy[i];
                            if( tx < 0 || tx >= line[0].size() || ty < 0 || ty >= line.size() || line[ty][tx] == '1') continue;
                            int next = id(tx+dx[i],ty+dy[i]);
                            if( tmp[next] == -1 ){
                                tmp[next]=tmp[q]+1;
                                Q.push(next);
                            }
                        }
                    }
                     
                    if( tmp[g] != -1 ) 
                        dir[y][x][k] = tmp[g];
                    swap(c1,c2);
                }
                line[y][x] = '0';
            }
        }
         
        memset(done,0,sizeof(done));
         
        priority_queue<NODE> Q;
        Q.push(NODE(s,0,0));
        while(Q.size()){
            NODE q = Q.top(); Q.pop();
             
            if( q.cost > 905 ){
                break;
            }
            if( done[q.id][q.cost]++ ) continue;
             
            if( q.maximum > 1e8 ) continue;
            if( q.id == g ){
                cout << q.maximum << endl;
                goto veryok;
            }
            for(int i = 0 ; i < 4 ; i++){
                int tx = X(q.id) + dx[i];
                int ty = Y(q.id) + dy[i];
                if( tx < 0 || tx >= line[0].size() || ty < 0 || ty >= line.size() || line[ty][tx] == '1') continue;
                int next = id(tx+dx[i],ty+dy[i]);
                int cost = q.cost + 1;
                int maximum = q.cost;
                if( ty % 2 == 0 ){
                    if( dx[i] == 1 ) maximum += dir[ty][tx][0];
                    else             maximum += dir[ty][tx][1];
                }else{
                    if( dy[i] == 1 ) maximum += dir[ty][tx][0];
                    else             maximum += dir[ty][tx][1];
                }
                Q.push(NODE(next,cost,max(q.maximum,maximum)));
            }
        }
        cout << -1 << endl;
        veryok:;
        /*
        cout << 2*H-1 << " " << 2*W-1 << endl;
        cout << shortest[id(2*H-1,2*W-1)] << endl;
         
        for(int i = 0 ; i < 2*H-1 ; i++){
            for(int j = 0 ; j < 2*W ; j++){
                if( shortest[id(j,i)] == -1 ) printf("     ");
                else  printf("%5d(%d,%d)",shortest[id(j,i)],j,i);
            }
            cout << endl;
        }
        */
 
    }
     
}

Measured memory_bytes: 5044