import sys import heapq def main(): input = sys.stdin.buffer.readline h, w = map(int, input().split()) a = [] for _ in range(h): a.extend(map(int, input().split())) n = h * w shift = (n - 1).bit_length() mask = (1 << shift) - 1 # bit 0,1: 各色のヒープに追加済み # bit 2,3: 各色で塗られている state = bytearray(n) state[0] = 5 state[n - 1] = 10 p0, p1 = 1, w p2, p3 = n - w - 1, n - 2 state[p0] |= 1 state[p1] |= 1 state[p2] |= 2 state[p3] |= 2 heaps = [ [(a[p0] << shift) | p0, (a[p1] << shift) | p1], [(a[p2] << shift) | p2, (a[p3] << shift) | p3] ] for heap in heaps: heapq.heapify(heap) push = heapq.heappush pop = heapq.heappop for i in range(n): side = i & 1 seen = 1 << side mine = 4 << side other = 8 >> side heap = heaps[side] p = pop(heap) & mask state[p] |= mine x, y = divmod(p, w) if x > 0: q = p - w s = state[q] if s & other: print(i + 1) return if not (s & seen): state[q] = s | seen push(heap, (a[q] << shift) | q) if x + 1 < h: q = p + w s = state[q] if s & other: print(i + 1) return if not (s & seen): state[q] = s | seen push(heap, (a[q] << shift) | q) if y > 0: q = p - 1 s = state[q] if s & other: print(i + 1) return if not (s & seen): state[q] = s | seen push(heap, (a[q] << shift) | q) if y + 1 < w: q = p + 1 s = state[q] if s & other: print(i + 1) return if not (s & seen): state[q] = s | seen push(heap, (a[q] << shift) | q) main()