Shepherd's Sleep

Limits: 4 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk went to the field to pasture his stallions. The field has a rectangular shape and is divided into \(n \times m\) square plots. Each plot is given by a pair of numbers \((i, j)\), where \(1 \le i \le n, 1 \le j \le m\). Horses graze in some of the plots, at most one horse per plot.

The positions of the horses are given by a matrix \(a\) of size \(n \times m\). If \(a_{i, j} = 0\), then there is no horse on the plot \((i, j)\). Otherwise, \(a_{i, j}\) is equal to the size of the horse grazing on the plot \((i, j)\) (there are large and small horses on the farm).

The bigger the horse, the louder it neighs while grazing. They neigh so loudly that they can be heard across the entire field, not just on their own plot.

When Zenyk is at the plot \((x, y)\), he hears a horse grazing at the plot \((i, j)\) with a loudness equal to \[\max(0, a_{i, j} - (|x - i| + |y - j|)).\]

The noise level at the plot \((i, j)\) is the maximum loudness with which horses are heard at this plot. If no horse is heard at the plot, the noise level is zero.

Zenyk is going to have a nap soon. He will choose a plot on the field and sleep under the open sky. He wants to choose the quietest possible plot. Note that Zenyk can sleep on a plot where a stallion is grazing.

Find the minimum noise level among all plots of the field.

Input

The first line contains two integers \(n\) and \(m\) — the dimensions of the field.

The next \(n\) lines contain \(m\) integers \(a_{i, j}\) each — the sizes of the horses grazing on the field.

Output

In a single line, print an integer — the minimum noise level across all plots of the field.

Constraints

\(1 \le n \cdot m \le 2 \cdot 10^5\),

\(0 \le a_{i, j} \le 2 \cdot 10^5\).

Scoring consists of the following blocks:

• 1 point for each example from the statement,

• 16 points: \(n, m \le 74\),

• 36 points: \(n = 1\),

• 21 points: \(n + m \le 600\),

• 25 points: without additional constraints.

You will get the points for a block only if your program passes all tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 5 0 8 0 6 0 3 0 4 0 0 7	4

Input (stdin) сopy	Output (stdout) сopy
4 7 2 0 1 3 4 0 5 0 3 0 2 1 0 4 1 2 0 4 0 5 0 0 0 3 0 2 1 0	1

Notes

Let’s consider the first example.

• A horse of size \(5\) grazing at plot \((1, 1)\) can be heard with different loudness at different plots of the field. Here is the matrix indicating the loudness of this horse on the field: \(\begin{pmatrix} 5 & 4 & 3\\ 4 & 3 & 2\\ 3 & 2 & 1\\ 2 & 1 & 0 \end{pmatrix}\).

• For a horse of size \(8\) grazing at plot \((1, 3)\), the matrix will be: \(\begin{pmatrix} 6 & 7 & 8\\ 5 & 6 & 7\\ 4 & 5 & 6\\ 3 & 4 & 5 \end{pmatrix}\).

• For a horse of size \(6\) at plot \((2, 2)\) — \(\begin{pmatrix} 4 & 5 & 4\\ 5 & 6 & 5\\ 4 & 5 & 4\\ 3 & 4 & 3 \end{pmatrix}\).

• For a horse of size \(3\) at plot \((3, 1)\) — \(\begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & 2 & 1\\ 2 & 1 & 0 \end{pmatrix}\).

• For a horse of size \(4\) at plot \((3, 3)\) — \(\begin{pmatrix} 0 & 1 & 2\\ 1 & 2 & 3\\ 2 & 3 & 4\\ 1 & 2 & 3 \end{pmatrix}\).

• Finally, for a horse of size \(7\) at plot \((4, 3)\) — \(\begin{pmatrix} 2 & 3 & 4\\ 3 & 4 & 5\\ 4 & 5 & 6\\ 5 & 6 & 7 \end{pmatrix}\).

The matrix describing the noise level on the field — \(\begin{pmatrix} 6 & 7 & 8\\ 5 & 6 & 7\\ 4 & 5 & 6\\ 5 & 6 & 7 \end{pmatrix}\). The minimum value in this matrix is equal to \(4\) at cell \((3, 1)\).

In the second example, Zenyk can tuck into a corner at plot \((4, 1)\), where the noise level is \(1\).