Escaping the Barracks

Interview

Time limit1sMemory limit256 MB

Summary

Find the minimum level needed to walk from (0,0) to (n-1,m-1) on an n by m grid, using at most one jump that skips over exactly one block in a straight line.

Level: Medium5 of 10
Topics: Binary search, BFS, Graph, Array
Solved: No attempts yet

Problem

Giyun likes a game about escaping from the army. To finish the game he has to cross the barracks and get out. For the sake of discipline the barracks is always a rectangle of height $n$ and width $m$ .

Giyun starts on block $(0, 0)$ in the top left corner and has to reach block $(n-1, m-1)$ in the bottom right corner, moving only up, down, left, and right. He may never leave the barracks while moving, and he must step on block $(0, 0)$ and on block $(n-1, m-1)$ .

Every block has a level requirement. If the number written on a block is $3$ , Giyun needs level $3$ or higher to step on that block.

Giyun can use the air force's special equipment once per game. The equipment carries him from the block he is standing on over one block in a single direction, and he lands on the block two steps away in that direction. He does not step on the block he passes over, so its level requirement does not apply. Two conditions hold.

He cannot change direction in the middle of the jump.
The block he lands on has to be inside the barracks.

Find the lowest level Giyun needs in order to escape the barracks.

Input

The first line contains the height $n$ and the width $m$ of the barracks. ( $1 \le n, m \le 100$ )

Each of the next $n$ lines contains $m$ level requirements, given from the top row down. Every level requirement $k$ satisfies $0 \le k \le 10^9$ .

Output

Print the lowest level Giyun has to reach in order to escape the barracks.

Examples2

Example 1
Input
```
4 3
2 5 2
3 4 3
12 1 3
1 3 2
```
Expected output
```
3
```
Example 2
Input
```
1 3
1 1000000000 2
```
Expected output
```
2
```