#include <iostream>
#include <vector>
using namespace std;

int h,w;
int door_ver[30][29];
int door_side[29][30];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};

int check( int x_start, int y_start, int x_end, int y_end ) {

  if ( x_start == x_end && y_start == y_end ) return 0;

  int map[30][30] = {0};
  vector<int> x_old,y_old,x_new,y_new;
  map[x_start][y_start] = 1;
  x_old.push_back(x_start);
  y_old.push_back(y_start);

  while(true) {

    for ( int i = 0; i < x_old.size(); i++ ) {
      for ( int j = 0; j < 4; j++ ) {

	int x = x_old[i]+dx[j];
	int y = y_old[i]+dy[j];
	if ( x < 0 || x >= w || y < 0 || y >= h ) continue;
	if ( map[x][y] != 0 ) continue;

	if ( j == 0 && door_side[x_old[i]-1][y_old[i]] == 1 ) continue;
	if ( j == 1 && door_side[x_old[i]][y_old[i]] == 1 ) continue;
	if ( j == 2 && door_ver[x_old[i]][y_old[i]-1] == 1 ) continue;
	if ( j == 3 && door_ver[x_old[i]][y_old[i]] == 1 ) continue;

	if ( x == x_end && y == y_end ) return map[x_old[i]][y_old[i]];
	map[x][y] = map[x_old[i]][y_old[i]]+1;
	x_new.push_back(x);
	y_new.push_back(y);

      }
    }

    if ( x_new.size() == 0 ) return -1;
    x_old.clear();
    y_old.clear();
    for ( int i = 0; i < x_new.size(); i++ ) {
      x_old.push_back(x_new[i]);
      y_old.push_back(y_new[i]);
    }
    x_new.clear();
    y_new.clear();

  }
  return 0;
}

int main() {

  while(true) {

    cin >> h >> w;
    if ( h == 0 ) break;

    for ( int i = 0; i < h; i++ ) {
      for ( int j = 0; j < w-1; j++ ) {
	cin >> door_side[j][i];
      }
      if ( i == h-1 ) break;
      for ( int j = 0; j < w; j++ ) {
	cin >> door_ver[j][i];
      }
    }

    int map[30][30] = {0};
    for ( int i = 0; i < h; i++ ) {
      for ( int j = 0; j < w; j++ ) {

	if ( check( 0, 0, j, i ) == -1 ) continue;

	int cnt = 0;
	int cnt_max = 0;
	if ( j != 0 ) {
	  if ( door_side[j-1][i] == 0 ) {
	    door_side[j-1][i] = 1;
	    cnt = check( j, i, w-1, h-1 );
	    door_side[j-1][i] = 0;
	    if ( cnt == -1 ) {
	      map[j][i] = -1;
	      continue;
	    }
	    cnt_max = max( cnt_max, cnt );
	  }
	}
	if ( j != w-1 ) {
	  if ( door_side[j][i] == 0 ) {
	    door_side[j][i] = 1;
	    cnt = check( j, i, w-1, h-1 );
	    door_side[j][i] = 0;
	    if ( cnt == -1 ) {
	      map[j][i] = -1;
	      continue;
	    }
	    cnt_max = max( cnt_max, cnt );
	  }
	}
	if ( i != 0 ) {
	  if ( door_ver[j][i-1] == 0 ) {
	    door_ver[j][i-1] = 1;
	    cnt = check( j, i, w-1, h-1 );
	    door_ver[j][i-1] = 0;
	    if ( cnt == -1 ) {
	      map[j][i] = -1;
	      continue;
	    }
	    cnt_max = max( cnt_max, cnt );
	  }
	}
	if ( i != h-1 ) {
	  if ( door_ver[j][i] == 0 ) {
	    door_ver[j][i] = 1;
	    cnt = check( j, i, w-1, h-1 );
	    door_ver[j][i] = 0;
	    if ( cnt == -1 ) {
	      map[j][i] = -1;
	      continue;
	    }
	    cnt_max = max( cnt_max, cnt );
	  }
	}

      	map[j][i] = cnt_max;

      }
    }

    int map2[30][30] = {0};
    vector<int> x_old,y_old,x_new,y_new;
    map2[0][0] = map[0][0];
    x_old.push_back(0);
    y_old.push_back(0);
    int cnt = 0;

    while(true) {
      cnt++;

      for ( int i = 0; i < x_old.size(); i++ ) {
	for ( int j = 0; j < 4; j++ ) {

	  int x = x_old[i]+dx[j];
	  int y = y_old[i]+dy[j];
	  if ( x < 0 || x >= w || y < 0 || y >= h ) continue;
	  if ( map[x][y] == -1 ) continue;

	  if ( j == 0 && door_side[x_old[i]-1][y_old[i]] == 1 ) continue;
	  if ( j == 1 && door_side[x_old[i]][y_old[i]] == 1 ) continue;
	  if ( j == 2 && door_ver[x_old[i]][y_old[i]-1] == 1 ) continue;
	  if ( j == 3 && door_ver[x_old[i]][y_old[i]] == 1 ) continue;

	  bool flag = false;
	  if ( map2[x][y] != 0 ) {
	    if ( map2[x_old[i]][y_old[i]] < map2[x][y] ) {
	      flag = true;
	    }
	  }else {
	    flag = true;
	  }
	  if ( flag ) {
	    map2[x][y] = max( cnt + map[x][y], map2[x_old[i]][y_old[i]] );
	    x_new.push_back(x);
	    y_new.push_back(y);
	  }

	}
      }

      if ( x_new.size() == 0 ) break;
      x_old.clear();
      y_old.clear();
      for ( int i = 0; i < x_new.size(); i++ ) {
	x_old.push_back(x_new[i]);
	y_old.push_back(y_new[i]);
      }
      x_new.clear();
      y_new.clear();

    }

    if ( map2[w-1][h-1] > 0 ) {
      cout << map2[w-1][h-1] << endl;
    }else {
      cout << "-1" << endl;
    }

  }
  return 0;
}

Measured memory_bytes: 1244