#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001

struct state {
    P p;
    int c, d;
};
bool operator<(const state &a, const state &b) {
    if (a.c != b.c) return a.c > b.c;
    return a.d > b.d;
}

int h, w;
int wall[30][30][30][30];
int dist[4][30][30][30][30];
int dp[30][30][1800];
int dd[] = {-1, 0, 1, 0, -1};

bool range(int y, int x) {
    return 0 <= y && y < h && 0 <= x && x < w;
}

void bfs(int d[30][30], int si, int sj) {
    rep(i, 30)rep(j, 30) d[i][j] = INF;

    queue<PIP> q;
    q.push(PIP(0, P(si, sj)));
    while(q.size()) {
        PIP p = q.front(); q.pop();
        int i = p.se.fi, j = p.se.se, c = p.fi;
        if (d[i][j] < INF) continue;
        d[i][j] = c;
        rep(dir, 4) {
            int ni = i + dd[dir], nj = j + dd[dir + 1];
            if (range(ni, nj) && !wall[i][j][ni][nj] && d[ni][nj] == INF) {
                q.push(PIP(c + 1, P(ni, nj)));
            }
        }
    }
}

int main(){
    cin.sync_with_stdio(false);
    while(cin >> h >> w, h | w) {
        rep(i, 2 * h - 1) {
            int ii = i / 2, t;
            if (i % 2) {
                rep(j, w) {
                    cin >> t;
                    wall[ii][j][ii + 1][j] = wall[ii + 1][j][ii][j] = t;
                }
            } else {
                rep(j, w - 1) {
                    cin >> t;
                    wall[ii][j][ii][j + 1] = wall[ii][j + 1][ii][j] = t;
                }
            }
        }

        bool ok = true;
        rep(i, h)rep(j, w) {
            rep(dir, 4) {
                int ni = i + dd[dir], nj = j + dd[dir + 1];
                if (range(ni, nj) && !wall[i][j][ni][nj]) {
                    wall[i][j][ni][nj] = wall[ni][nj][i][j] = 1;
                    bfs(dist[dir][i][j], h - 1, w - 1);
                    if (dist[dir][i][j][i][j] == INF) ok = false;
                    wall[i][j][ni][nj] = wall[ni][nj][i][j] = 0;
                }
            }
        }

        int ans = -1;
        priority_queue<state> q;
        q.push((state){P(0, 0), 0, 0});
        rep(i, h)rep(j, w)rep(k, h * w * 2) dp[i][j][k] = INF;
        while(q.size()) {
            state s = q.top(); q.pop();
            int i = s.p.fi, j = s.p.se;
            if (dp[i][j][s.d] < INF || s.d == h * w * 2 - 1) continue;
            if (i == h - 1 && j == w - 1) {
                ans = s.c;
                break;
            }
            dp[i][j][s.d] = s.c;
            rep(dir, 4) {
                int ni = i + dd[dir], nj = j + dd[dir + 1];
                if (range(ni, nj) && !wall[i][j][ni][nj] && dp[ni][nj][s.d + 1] == INF && dist[dir][i][j][i][j] < INF) {
                    q.push((state){P(ni, nj), max(s.c, s.d + dist[dir][i][j][i][j]), s.d + 1});
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 25060