#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;
typedef pair<int,int> pii;

struct P {
  int y, x, d, cost;
  P(int y, int x, int d, int cost) :
    y(y),x(x),d(d),cost(cost) {}
  bool operator<(const P &b) const  {
    return cost > b.cost;
  }
};

bool can[30][30][4];
int dist[30][30];
int cost[30][30][4];
int dist2[30][30][910];

int main() {
  int h, w;
  while(cin>>h>>w,h||w) {
    memset(can,0,sizeof(can));
    REP(i,2*h-1) {
      if (i&1) {
        REP(j,w) {
          bool f;
          cin >> f;
          can[i/2][j][2] = can[i/2+1][j][0] = !f;
        }
      } else {
        REP(j,w-1) {
          bool f;
          cin >> f;
          can[i/2][j][1] = can[i/2][j+1][3] = !f;
        }
      }
    }
    // REP(i,h) {
    //   REP(j,w) {
    //     cout << "(";
    //     REP(k,4) cout << can[i][j][k];
    //     cout << ")";
    //   }
    //   cout << endl;
    // }
    const int dy[] = {-1,0,1,0};
    const int dx[] = {0,1,0,-1};
    REP(i,h) {
      REP(j,w) {
        REP(k,4) {
          if (can[i][j][k] == 0) continue;
          can[i][j][k] = 0;
          
          memset(dist,-1,sizeof(dist));
          dist[i][j] = 0;
          queue<pii> Q;
          Q.push(pii(i,j));
          while(!Q.empty()) {
            pii p = Q.front(); Q.pop();
            REP(d,4) {
              if (can[p.first][p.second][d]) {
                int yy = p.first + dy[d];
                int xx = p.second + dx[d];
                if (dist[yy][xx] == -1) {
                  dist[yy][xx] = dist[p.first][p.second] + 1;
                  Q.push(pii(yy,xx));
                }
              }
            }
          }
          if (dist[h-1][w-1] == -1) cost[i][j][k] = INF;
          else cost[i][j][k] = dist[h-1][w-1];
          can[i][j][k] = 1;
        }
      }
    }
    // REP(i,h) {
    //   REP(j,w) {
    //     cout << "(";
    //     REP(k,4) cout << cost[i][j][k] <<",";
    //     cout << ")";
    //   }
    //   cout << endl;
    // }    
    REP(i,h)REP(j,w)REP(k,h*w+10)dist2[i][j][k]=INF;
    priority_queue<P> Q;
    Q.push(P(0,0,0,0));
    int ans = INF;
    while(!Q.empty()) {
      P p = Q.top(); Q.pop();
      if (dist2[p.y][p.x][p.d] < p.cost) continue;
      // cout << p.y << " " << p.x << " " << p.d << " " << p.cost << endl;
      if (p.y == h-1 && p.x == w-1) {
        ans = min(ans, p.cost);
      }
      REP(i,4) {
        if (!can[p.y][p.x][i]) continue;
        int yy = p.y + dy[i];
        int xx = p.x + dx[i];
        int co = cost[p.y][p.x][i];
        int ncost = max(p.cost, p.d+co);
        if (dist2[yy][xx][p.d+1] > ncost) {
          dist2[yy][xx][p.d+1] = ncost;
          Q.push(P(yy,xx,p.d+1,ncost));
        }
      }
    }
    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;
  }
}

Measured memory_bytes: 4496