Сон пастуха

Обмеження: 4 сек., 512 МіБ

Зеник пішов на поле пасти своїх жеребців. Поле має форму прямокутника та поділене на $n \times m$ квадратних ділянок. Кожна ділянка задається парою чисел $(i, j)$, де $1 \le i \le n, 1 \le j \le m$. У деяких ділянках поля пасуться коні, щонайбільше по одному коню на кожній ділянці.

Розташування коней задано матрицею $a$ розміру $n \times m$. Якщо $a_{i, j} = 0$, то на ділянці поля $(i, j)$ немає коня. Інакше $a_{i, j}$ дорівнює розміру коня, що пасеться на ділянці $(i, j)$ (на фермі є великі й малі коні).

Чим більший кінь, тим гучніше він ірже, коли пасеться. Вони іржуть так голосно, що їх може бути чутно на все поле, а не лише на їхній ділянці.

Коли Зеник перебуває на ділянці $(x, y)$, він чує коня, що пасеться на ділянці $(i, j)$ з гучністю, що дорівнює $$\max(0, a_{i, j} - (|x - i| + |y - j|)).$$

Рівень шуму на ділянці $(i, j)$ — це максимальна гучність, з якою чутно коней на цій ділянці. Якщо на ділянці не чутно жодного коня, то рівень шуму дорівнює нулю.

У Зеника скоро обідній сон. Він вибере собі ділянку на полі й буде спати просто неба. Він хоче вибрати якомога тихішу ділянку. Зауважте, що Зеник може спати на ділянці, де пасеться жеребець.

Знайдіть мінімальний рівень шуму з-поміж усіх ділянок поля.

Вхідні дані

У першому рядку задано два цілі числа $n$ і $m$ — розміри поля.

У наступних $n$ рядках задано по $m$ цілих чисел $a_{i, j}$ — розміри коней, що пасуться на полі.

Вихідні дані

В одному рядку виведіть ціле число — мінімальний рівень шуму на всіх ділянках поля.

Обмеження

$1 \le n \cdot m \le 2 \cdot 10^5$,

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

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 16 балів: $n, m \le 74$,

• 36 балів: $n = 1$,

• 21 балів: $n + m \le 600$,

• 25 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 5 0 8 0 6 0 3 0 4 0 0 7	4

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
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

Примітки

Розгляньмо перший приклад.

• Коня розміром $5$, що пасеться на ділянці $(1, 1)$, чутно з різною гучністю на різних ділянках поля. Ось матриця, що вказує гучність цього коня на полі: $\begin{pmatrix} 5 & 4 & 3\\ 4 & 3 & 2\\ 3 & 2 & 1\\ 2 & 1 & 0 \end{pmatrix}$.

• Для коня розміром $8$, що пасеться на ділянці $(1, 3)$, матриця буде такою: $\begin{pmatrix} 6 & 7 & 8\\ 5 & 6 & 7\\ 4 & 5 & 6\\ 3 & 4 & 5 \end{pmatrix}$.

• Для коня розміром $6$ на ділянці $(2, 2)$ — $\begin{pmatrix} 4 & 5 & 4\\ 5 & 6 & 5\\ 4 & 5 & 4\\ 3 & 4 & 3 \end{pmatrix}$.

• Для коня розміром $3$ на ділянці $(3, 1)$ — $\begin{pmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 3 & 2 & 1\\ 2 & 1 & 0 \end{pmatrix}$.

• Для коня розміром $4$ на ділянці $(3, 3)$ — $\begin{pmatrix} 0 & 1 & 2\\ 1 & 2 & 3\\ 2 & 3 & 4\\ 1 & 2 & 3 \end{pmatrix}$.

• Нарешті, для коня розміром $7$ на ділянці $(4, 3)$ — $\begin{pmatrix} 2 & 3 & 4\\ 3 & 4 & 5\\ 4 & 5 & 6\\ 5 & 6 & 7 \end{pmatrix}$.

Матриця, що описує рівень шуму на полі — $\begin{pmatrix} 6 & 7 & 8\\ 5 & 6 & 7\\ 4 & 5 & 6\\ 5 & 6 & 7 \end{pmatrix}$. Мінімальне значення в цій матриці рівне $4$ в клітинці $(3, 1)$.

У другому прикладі Зеник може забитися в куточок на ділянці $(4, 1)$, де рівень шуму — $1$.