[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/tap2013-problems.pdf]

Finding the treasures hidden centuries ago by the pirates of the Caribbean islands is no easy task, but even more difficult is living to tell the story. This is because, as everybody knows, pirates had supernatural powers which they used to curse the person who took their treasure unauthorized.

A very common curse among the most powerful of pirates, and for which it is always a good idea to be prepared, is known today as the deadly mist. Whenever a pirate's treasure is found, this curse will make a poisonous mist lift from the ground until the whole island gets covered by it. Any living creature that is touched by the mist will die instantly, something especially undesirable for those who have just found a treasure. The only way to save yourself is then to return to your boat, always going through areas that have not yet been covered by the mist, and thus flee with that part of the treasure that may have been rescued. In this problem we are interested in knowing what's the maximum amount of time that one can take to collect the treasure in such a way so as to be able to return to the boat alive.

To simplify the problem, we will consider that an island can be represented by a grid with R rows and C columns, in which the cell in the i-th row and the j-th column has height H_ij above sea level. Furthermore, we will assume that the treasure is always hidden in the cell in row 1 and column 1, because this is the one furthest away from the only place where the boat can set anchor, which is the cell in row R and column C. The deadly mist appears at sea level at the very same instant that the treasure is found, and then rises on all the island at a rate of one unit of height per second, so that after t seconds one cannot be in any cell of height less or equal to t. In order to return to the boat, you may go from one cell to another only if they share a side, so that if you are on a given cell you can only move horizontally to the cell before or after it in the same row, or vertically to the cell before or after it in the same column, but you cannot move diagonally or cross the boundaries of the island. Each such movement from one cell to another takes exactly one second.

Input

The first line contains two integer numbers R and C, respectively the number of rows and columns of the grid that represents the island, which consists of at least two cells (1 ≤ R, C ≤ 500 and R×C ≥ 2). Each of the following R lines contains C values. In the i-th of these R lines, the j-th value is an integer H_ij representing the height of the cell at row i and column j (1 ≤ H_ij ≤ 10⁶ for i = 1, ..., R and j = 1, ..., C).

Output

Print a single line containing an integer number representing the maximum amount of time in seconds that one can take to collect the treasure, so as to be able to return to the boat without being reached by the deadly mist. Print the number -1 if it is impossible to return to the boat even if one starts the way back as soon as the treasure is discovered.

Example 1

Input:
3 3
2 3 4
3 4 5
4 5 6

Output:
1

Example 2

Input:
3 3
1 2 3
2 2 3
2 4 5

Output:
-1

Example 3

Input:
3 2
1000000 1000000
1000000 1000000
1000000 314

Output:
310