#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

int H, W;
int A[2][31][31];

const int dy[] = {-1, 0, 0, 1};
const int dx[] = {0, -1, 1, 0};
int from_goal_distance[2][31][31][31][31];
int ans[31][31];
const int INF = 1 << 29;

// cy,cx??????ang????§????????????¨????????????????£????index????¨????
tpl get_index(int cy, int cx, int ang){
  int ny = dy[ang] + cy;
  int nx = dx[ang] + cx;
  if(ny >= 0 && nx >= 0 && ny < H && nx < W){
    if(dx[ang] > 0) return make_tuple(0, cy, cx);
    else if(dx[ang] < 0) return make_tuple(0, cy, cx-1);
    else if(dy[ang] > 0) return make_tuple(1, cy, cx);
    else return make_tuple(1, cy-1, cx);
  }
  return make_tuple(-1,-1,-1);
}

// ?§??????????????????????
bool is_move(int cy, int cx, int k){
  tpl t = get_index(cy,cx,k);
  if(get<0>(t)==-1)return false;
  // ?£???????
  return !(A[get<0>(t)][get<1>(t)][get<2>(t)]);
}

void bfs(int sy, int sx, int d[31][31]){
  for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++)
      d[i][j] = INF;
  queue<pii> q;
  q.push(pii(sy, sx));
  d[sy][sx] = 0;
  while(q.size()){
    pii p = q.front(); q.pop();
    int cy = p.first;
    int cx = p.second;
    int ccost = d[cy][cx];
    for(int i = 0; i < 4; i++){
      if(is_move(cy, cx, i)){
        int ny = cy + dy[i];
        int nx = cx + dx[i];
        if(d[ny][nx] == INF){
          q.push(pii(ny,nx));
          d[ny][nx] = ccost + 1;
        }
      }
    }
  }
}

void dijkstra(int sy, int sx, int d[31][31]){
  for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++)
      d[i][j] = INF;
  priority_queue<pair<int, pii>, vector<pair<int, pii> >, greater<pair<int, pii> > > pq;
  d[sy][sx] = 0;
  pq.push(make_pair(0, pii(sy, sx)));
  while(pq.size()){
    pair<int, pii> p = pq.top(); pq.pop();
    int ccost = p.first;
    int cy = p.second.first;
    int cx = p.second.second;
    if(d[cy][cx] < ccost) continue;
    for(int i = 0; i < 4; i++){
      if(is_move(cy, cx, i)){
        int ny = cy + dy[i];
        int nx = cx + dx[i];
        // ?????¨?????´?????????1?????????????????????????????¨, (ny,nx)??????goal?????§????????????????????§????????????
        tpl t = get_index(cy, cx, i);
        int ncost = max(ccost + 1, from_goal_distance[get<0>(t)][get<1>(t)][get<2>(t)][ny][nx]);
        if(d[ny][nx] > ncost){
          d[ny][nx] = ncost;
          pq.push(make_pair(ncost, pii(ny, nx)));
        }
      }
    }
  }
}

int main(){

  while(cin>>H>>W && (H|W)){
    for(int i = 0; i < 2 * H - 1; i++){
      int *ary = A[i%2][i/2];
      for(int j = 0; j < W - ((i % 2) == 0); j++) cin>>ary[j];
    }
    // ?????´???????£???????????????????????????????????¨????
    for(int i = 0; i < 2 * H - 1; i++){
      for(int j = 0; j < W - ((i % 2) == 0); j++){
        // ?£????????????´???, ?£????switching
        if(A[i%2][i/2][j] == 0){
          A[i%2][i/2][j] ^= 1;
          bfs(H-1, W-1, from_goal_distance[i%2][i/2][j]);
          A[i%2][i/2][j] ^= 1;
        }
        else{
          bfs(H-1, W-1, from_goal_distance[i%2][i/2][j]);
        }
      }
    }
    // ??´????????????dijkstra?????????????§£????¨????
    dijkstra(H-1, W-1, ans); 
    if(ans[0][0] == INF)cout<<-1<<endl;
    else cout<<ans[0][0]<<endl;
  }
  return 0;
}

Measured memory_bytes: 9912