#include<iostream>
#include<vector>
#include<bitset>
#include<queue>
#include<tuple>
#include<functional>
#include<algorithm>
using namespace std;

enum {N, E, S, W};
const unsigned long ALL = 1 + 2 + 4 + 8;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

const int INF = 1000000;

enum {Y, X, STEP};
typedef tuple<int, int, int> Node;

enum {DWORST, DSTEP, DY, DX};
typedef tuple<int, int, int, int> DNode;

vector<vector<vector<int>>> memo;

int h, w;
vector<vector<bitset<4>>> wall;

int bfs(int by, int bx, int bd) {
    queue<Node> q;
    vector<vector<int>> visited(h, vector<int>(w, 0));
    q.push(Node(by, bx, 0));
    while(!q.empty()) {
        int y = get<Y>(q.front());
        int x = get<X>(q.front());
        int step = get<STEP>(q.front());
        q.pop();
        if(y == h - 1 && x == w - 1) return step;
        if(visited[y][x]) continue;
        visited[y][x] = 1;
        for(int d = 0; d < 4; ++d) {
            if(wall[y][x][d]) continue;
            if(y == by && x == bx && d == bd) continue;
            int ny = y + dy[d];
            int nx = x + dx[d];
            if(ny < 0 || h <= ny || nx < 0 || w <= nx) continue;
            q.push(Node(ny, nx, step + 1));
        }
    }
    return INF;
}

int Dijkstra() {
    priority_queue<DNode, vector<DNode>, greater<DNode>> q;
    q.push(DNode(0, 0, 0, 0));
    vector<vector<vector<int>>> visited(h, vector<vector<int>>(w, vector<int>(h * w * 2, 0)));
    while(!q.empty()) {
        int y = get<DY>(q.top());
        int x = get<DX>(q.top());
        int step = get<DSTEP>(q.top());
        int worst = get<DWORST>(q.top());
        q.pop();
        if(y == h - 1 && x == w - 1) return worst;
        if(visited[y][x][step]) continue;
        visited[y][x][step] = 1;
        for(int d = 0; d < 4; ++d) {
            if(wall[y][x][d]) continue;
            int ny = y + dy[d];
            int nx = x + dx[d];
            if(ny < 0 || h <= ny || nx < 0 || w <= nx) continue;
            int nworst = max({step + 1, worst, step + memo[y][x][d]});
            q.push(DNode(nworst, step + 1, ny, nx));
        }
    }
    return INF;
}

int main() {
    while(cin >> h >> w, h | w) {
        wall = vector<vector<bitset<4>>>(h, vector<bitset<4>>(w, bitset<4>(ALL)));
        for(int i = 0; i < h - 1; ++i) {
            for(int j = 0; j < w - 1; ++j) {
                int is_wall;
                cin >> is_wall;
                if(is_wall) continue;
                wall[i][j].reset(E);
                wall[i][j + 1].reset(W);
            }
            for(int j = 0; j < w; ++j) {
                int is_wall;
                cin >> is_wall;
                if(is_wall) continue;
                wall[i][j].reset(S);
                wall[i + 1][j].reset(N);
            }
        }
        for(int j = 0; j < w - 1; ++j) {
            int is_wall;
            cin >> is_wall;
            if(is_wall) continue;
            wall[h - 1][j].reset(E);
            wall[h - 1][j + 1].reset(W);
        }

        memo = vector<vector<vector<int>>>(h, vector<vector<int>>(w, vector<int>(4, INF)));
        for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) for(int d = 0; d < 4; ++d) memo[i][j][d] = bfs(i, j, d);

        int answer = Dijkstra();
        cout << (answer < INF ? answer : -1) << endl;
    }
}

Measured memory_bytes: 7828