J. Dangerous Maze
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In an abandoned industrial complex, represented by a grid of $$$M$$$ rows and $$$N$$$ columns, each cell $$$(i, j)$$$ has an altitude $$$h_{i,j}$$$. A toxic gas begins to fill the complex. If the gas reaches a height $$$H$$$, all cells whose altitude is strictly less than $$$H$$$ become impassable ($$$h_{i,j} \lt H$$$). Cells where $$$h_{i,j} \ge H$$$ remain safe.

You are initially at cell $$$(1, 1)$$$ (top left) and must reach the exit located at cell $$$(M, N)$$$ (bottom right). You can move horizontally or vertically between two adjacent cells, provided that both cells are passable.

Your goal is to determine the maximum value of $$$H$$$ such that there still exists a path between the entrance and the exit. Note that the entrance and the exit themselves must also be passable.

Input

The first line contains two integers $$$M$$$ and $$$N$$$ ($$$1 \le M, N \le 500$$$). The next $$$M$$$ lines each contain $$$N$$$ integers $$$h_{i,j}$$$ ($$$0 \le h_{i,j} \le 10^9$$$).

Output

A single integer: the maximum gas height $$$H$$$.

Example
Input
3 3
10 5 8
2 3 12
15 10 10
Output
5