/*
 * by purple
 * at 12-01-01 13:05:26
 */

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

#define sz(x) ((int)((x).size()))
#define out(x) printf(#x" %d\n", x)
#define rep(i,n) for(int i=0;i<(n);++i)
#define repf(i,a,b) for(int i=(a);i<=(b);++i)

const int maxn = 32;
const int inf = 1024;

int c[maxn][maxn][2];
int dis[maxn][maxn];
int opt[maxn][maxn];
int n, m;

int gao(int x, int y) {
    queue<int> q;
    memset (dis, -1, sizeof(dis));
    dis[x][y] = 0;
    q.push(x), q.push(y);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        int y = q.front(); q.pop();
        if (x == n - 1 && y == m - 1) {
            return dis[x][y];
        }
        if (x > 0 && !c[x - 1][y][1] && dis[x - 1][y] == -1) {
            dis[x - 1][y] = dis[x][y] + 1;
            q.push(x - 1), q.push(y);
        }
        if (x < n - 1 && !c[x][y][1] && dis[x + 1][y] == -1) {
            dis[x + 1][y] = dis[x][y] + 1;
            q.push(x + 1), q.push(y);
        }
        if (y > 0 && !c[x][y - 1][0] && dis[x][y - 1] == -1) {
            dis[x][y - 1] = dis[x][y] + 1;
            q.push(x), q.push(y - 1);
        }
        if (y < m - 1 && !c[x][y][0] && dis[x][y + 1] == -1) {
            dis[x][y + 1] = dis[x][y] + 1;
            q.push(x), q.push(y + 1);
        }
    }
    return inf;
}

void update(int& x, int y) {
    if (x == -1 || x > y) x = y;
}

int gao() {
    rep (i, n) rep (j, m) {
        opt[i][j] = inf;
    }
    opt[n - 1][m - 1] = 0;
    while (true) {
        bool f = false;
        rep (i, n) rep (j, m) {
            int now = opt[i][j];
            if (i > 0 && !c[i - 1][j][1] && opt[i - 1][j] + 1 < opt[i][j]) {
                c[i - 1][j][1] = true;
                update (now, max(opt[i - 1][j] + 1, gao(i, j)));
                c[i - 1][j][1] = false;
            }
            if (i < n - 1 && !c[i][j][1] && opt[i + 1][j] + 1 < opt[i][j]) {
                c[i][j][1] = true;
                update (now, max(opt[i + 1][j] + 1, gao(i, j)));
                c[i][j][1] = false;
            }
            if (j > 0 && !c[i][j - 1][0] && opt[i][j - 1] + 1 < opt[i][j]) {
                c[i][j - 1][0] = true;
                update (now, max(opt[i][j - 1] + 1, gao(i, j)));
                c[i][j - 1][0] = false;
            }
            if (j < m - 1 && !c[i][j][0] && opt[i][j + 1] + 1 < opt[i][j]) {
                c[i][j][0] = true;
                update (now, max(opt[i][j + 1] + 1, gao(i, j)));
                c[i][j][0] = false;
            }
            if (now != opt[i][j]) {
                opt[i][j] = now;
                f = true;
            } 
        }
        if (!f) {
            break;
        }
    }
    return opt[0][0] == inf? -1 : opt[0][0];
}

int main() {
    while (scanf ("%d%d", &n, &m), n || m) {
        rep (i, n - 1) {
            rep (j, m - 1) {
                scanf ("%d", &c[i][j][0]);
            }
            rep (j, m) {
                scanf ("%d", &c[i][j][1]);
            }
        }
        rep (j, m - 1) {
            scanf ("%d", &c[n - 1][j][0]);
        }
        printf ("%d\n", gao());
    }
    return 0;
}

Measured memory_bytes: 844