Liam is planning out his route for an upcoming nature hike. Unfortunately, the region that he plans on hiking through is notoriously muddy, so in order to prevent his floral shirt from getting covered with mud, he has decided to pick a route for which the maximum depth of mud encountered is minimized.

The terrain is modelled as a two-dimensional grid, with nonnegative integers giving the depth of the mud in each cell in micrometers (millionths of a meter). The hike must begin at one of the cells in the leftmost column of the grid and finish at one of the cells in the rightmost column of the grid. Liam is allowed to move either north, south, east, or west, but he cannot travel diagonally.

-----Input-----
The first line of input contains two space-separated integers, $r$ and $c$ $(2 \leq r, c \leq 1000)$, indicating the number of rows and the number of columns in the grid, respectively. Each of the next $r$ lines contains $c$ space-separated integers, indicating the depth of mud in the cells of the corresponding grid row from left to right. Each depth is measured in micrometers and is given as an integer in the interval $[0,1000000]$.

-----Output-----
The output should contain a single integer, the depth of the deepest mud that Liam is forced to hike through if his route minimizes this value.

-----Examples-----
Sample Input 1:
5 4
2 1 0 8
3 7 3 5
3 1 2 4
9 0 4 6
5 3 2 3
Sample Output 1:
3

Sample Input 2:
2 2
3 0
1 2
Sample Output 2:
2

见题面

见题面