군대 탈출하기

기윤이는 군대 탈출 게임을 좋아한다. 이 게임을 끝내려면 병영을 가로질러 밖으로 나가야 한다. 병영은 군기를 위해 언제나 세로 $n$, 가로 $m$인 직사각형이다.

기윤이는 왼쪽 위 블록 $(0, 0)$에서 출발해 상하좌우 네 방향으로만 움직여 오른쪽 아래 블록 $(n-1, m-1)$에 도착해야 한다. 움직이는 동안 병영 밖으로 나갈 수 없고, 블록 $(0, 0)$과 블록 $(n-1, m-1)$은 반드시 밟는다.

블록마다 레벨 제한이 있다. 블록에 적힌 수가 $3$이면 레벨이 $3$ 이상이어야 그 블록을 밟을 수 있다.

기윤이는 공군의 특수장비를 게임당 한 번 쓸 수 있다. 특수장비를 쓰면 지금 서 있는 블록에서 한 방향으로 블록 하나를 건너뛰어 그 방향으로 두 칸 떨어진 블록에 내려선다. 건너뛴 블록은 밟지 않으므로 그 블록의 레벨 제한은 따지지 않는다. 조건은 두 가지다.

1. 건너뛰는 도중에 방향을 바꿀 수 없다.
2. 내려서는 블록이 병영 안에 있어야 한다.

기윤이가 병영을 탈출하려면 레벨이 최소 얼마여야 하는지 구하자.

첫째 줄에 병영의 세로 길이 $n$과 가로 길이 $m$이 주어진다. ($1 \le n, m \le 100$)

다음 $n$개 줄에 병영의 레벨 제한이 위쪽 줄부터 차례대로 한 줄에 $m$개씩 주어진다. 각 레벨 제한 $k$는 $0 \le k \le 10^9$를 만족한다.

기윤이가 병영을 탈출하기 위해 달성해야 하는 최소 레벨을 출력한다.