E. Rain
time limit per test
1 second
memory limit per test
256 mebibytes
input
standard input
output
standard output

In the magical kingdom of Equilibria, an unexpected storm occurred after a powerful spell. As a result, the lands between the Great Library of Equilibria and the trading district were flooded. Your hero, a young mage, must travel from the library to the market to deliver important scrolls with spells. The flooded fields of the kingdom form a grid of size $$$n \times m$$$, and each cell of the grid contains water of a certain depth. The mage can only move right, left, and down on the grid ($$$(\mathit{row}, \mathit{col} + 1)$$$, $$$(\mathit{row}, \mathit{col} - 1)$$$, and $$$(\mathit{row} + 1, \mathit{col})$$$), starting his journey from the upper left corner ($$$(1, 1)$$$, the library) and ending at the lower right corner ($$$(n, m)$$$, the market). Your task is to find such a path that the maximum depth of water along this path is the minimum possible, so that your hero remains as dry as possible.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 500$$$): the dimensions of Equilibria. Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$d_{i, j}$$$ ($$$0 \le d_{i, j} \le 10^9$$$, $$$d_{1, 1} = d_{n, m} = 0$$$), indicating the depth of water in each cell.

Output

Output the maximum depth of water on the path you found.

Examples
Input
3 3
0 1 9
9 1 9
9 1 0
Output
1
Input
5 3
0 1 1
9 9 2
1 1 1
2 9 9
1 1 0
Output
2