#include <iostream>
#include <vector>
#include <limits>
#include <array>
#include <algorithm>
#include <queue>
#include <tuple>

constexpr int Inf = std::numeric_limits<int>::max();

template <typename T>
using VecArr = std::vector<std::array<T, 4>>;

int main() {
	int h, w;
	
	while (true) {
		std::cin >> h >> w;
		if (h == 0 && w == 0)
			break;

		std::vector<VecArr<bool>> isWall(h, VecArr<bool>(w));
		for (int i = 0; i < w; ++i)
			isWall[0][i][0] = true;
		for (int i = 0; i < h; ++i)
			isWall[i][w - 1][1] = true;
		for (int i = 0; i < w; ++i)
			isWall[h - 1][i][2] = true;
		for (int i = 0; i < h; ++i)
			isWall[i][0][3] = true;
		

		for (int i = 0; i < 2 * h - 1; ++i) {
			for (int j = 0; j < (i % 2 == 0 ? w - 1 : w); ++j) {
				int d;
				std::cin >> d;

				if (i % 2 == 0)
					isWall[i / 2][j][1] = isWall[i / 2][j + 1][3] = d;
				else
					isWall[i / 2][j][2] = isWall[i / 2 + 1][j][0] = d;
			}
		}

		std::vector<VecArr<int>> costs(h, VecArr<int>(w, {Inf, Inf, Inf, Inf}));

		bool possible = true;
		for (int i = 0; i < h && possible; ++i) {
			for (int j = 0; j < w && possible; ++j) {
				auto calcCost = [&](int dir) {
					isWall[i][j][dir] = true;

					int ret = [&]() {
						std::queue<std::tuple<int, int, int>> que;
						std::vector<std::vector<bool>> visited(h, std::vector<bool>(w));

						que.emplace(i, j, 0);
						visited[i][j] = true;
						while (!que.empty()) {
							int y, x, depth;
							std::tie(y, x, depth) = que.front();
							que.pop();

							if (y == h - 1 && x == w - 1)
								return depth;

							const int dy[4] = { -1, 0, 1, 0 }, dx[4] = { 0, 1, 0, -1 };
							for (int k = 0; k < 4; ++k) {
								if (isWall[y][x][k])
									continue;

								const int ny = y + dy[k], nx = x + dx[k];
								if (visited[ny][nx])
									continue;

								visited[ny][nx] = true;
								que.emplace(ny, nx, depth + 1);
							}
						}

						if (visited[0][0])
							return Inf;
						else
							return Inf / 2;
					}();

					isWall[i][j][dir] = false;

					return ret;
				};

				for (int dir = 0; dir < 4; ++dir) {
					if (isWall[i][j][dir])
						continue;

					costs[i][j][dir] = calcCost(dir);

					if (costs[i][j][dir] == Inf) {
						std::cout << -1 << std::endl;
						possible = false;
					}
				}
			}
		}

		if (!possible)
			continue;

		auto isOK = [&](int threshold) {
			std::queue<std::tuple<int, int, int>> que;
			std::vector<std::vector<bool>> visited(h, std::vector<bool>(w));

			que.emplace(0, 0, 0);
			visited[0][0] = true;
			while (!que.empty()) {
				int y, x, c;
				std::tie(y, x, c) = que.front();
				que.pop();

				if (y == h - 1 && x == w - 1)
					return true;

				const int dy[4] = { -1, 0, 1, 0 }, dx[4] = { 0, 1, 0, -1 };
				for (int k = 0; k < 4; ++k) {
					if (isWall[y][x][k])
						continue;

					const int ny = y + dy[k], nx = x + dx[k];
					if (visited[ny][nx] || c + costs[y][x][k] > threshold)
						continue;

					visited[ny][nx] = true;
					que.emplace(ny, nx, c + 1);
				}
			}

			return false;
		};

		int l = 0, r = 2 * h * w;
		while (r - l > 1) {
			int mid = (l + r) / 2;
			if (isOK(mid))
				r = mid;
			else
				l = mid;
		}

		std::cout << r << std::endl;
	}
}


Measured memory_bytes: 3196