import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._
object Main extends App {

  solve()
  @tailrec def solve(): Unit = {
    val Array(h, w) = readLine.trim.split(' ').map(_.toInt)
    if (h == 0 && w == 0) return
    val rooms = Array.fill(h){Array.fill(w){Nil: List[Door]}}
    var doorCount = 0
    for (i ← 0 until 2 * h - 1) {
      val states = readLine.trim.split(' ').filter(_.nonEmpty).map{_ == "0"}
      i % 2 match {
        case 0 ⇒ for (j ← states.indices if states(j))  {
          rooms(i / 2)(j) ::= Door(Room(i / 2, j + 1), doorCount)
          rooms(i / 2)(j + 1) ::= Door(Room(i / 2, j), doorCount)
          doorCount += 1
        }
        case 1 ⇒ for (j ← states.indices if states(j)) {
          rooms(i / 2)(j) ::= Door(Room(i / 2 + 1, j), doorCount)
          rooms(i / 2 + 1)(j) ::= Door(Room(i / 2, j), doorCount)
          doorCount += 1
        }
      }
    }
    val byBrokenDoor = (0 until doorCount).map{id ⇒ countMinCost(rooms, id)}.toArray
    val worst = Array.tabulate(h){i ⇒ Array.tabulate(w){j ⇒ byBrokenDoor.map{_(i)(j)}.max}}
    if (byBrokenDoor.exists(a ⇒ a(0)(0) == Int.MaxValue)) {
      println(-1)
      solve()
    }else {
      var left = 0
      var right = h * w * 2
      while (left < right){
        val mid = (left + right) / 2
        if (canPass(rooms, worst, mid)) right = mid
        else left = mid + 1
      }
      println(right)
      solve()
    }
  }
  def canPass(rooms: Array[Array[List[Door]]], worst: Array[Array[Int]], k: Int): Boolean = {
    val count = Array.fill(rooms.length){Array.fill(rooms.head.length){Int.MaxValue}}
    val queue = mutable.Queue(Room(0, 0))
    count(0)(0) = 0
    while(queue.nonEmpty) {
      val current = queue.dequeue()
      for (Door(next, _) ← rooms(current.h)(current.w) if count(next.h)(next.w) == Int.MaxValue) {
        if (worst(next.h)(next.w) + count(current.h)(current.w) + 1 <= k) {
          count(next.h)(next.w) = count(current.h)(current.w) + 1
          queue.enqueue(next)
        }
      }
    }
    count.last.last <= k
  }
  def countMinCost(rooms: Array[Array[List[Door]]], invalid: Int): Array[Array[Int]] = {
    val count = Array.fill(rooms.length){Array.fill(rooms.head.length){Int.MaxValue}}
    val queue = mutable.Queue(Room(rooms.length - 1, rooms.head.length - 1))
    count(rooms.length - 1)(rooms.head.length - 1) = 0
    while (queue.nonEmpty) {
      val current = queue.dequeue()
      for (next ← rooms(current.h)(current.w) if next.id != invalid && count(next.to.h)(next.to.w) == Int.MaxValue) {
        count(next.to.h)(next.to.w) = count(current.h)(current.w) + 1
        queue.enqueue(next.to)
      }
    }
    count
  }
}
case class Door(to: Room, id: Int)
case class Room(h: Int, w: Int)

