Сон пастуха

Обмеження: 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\).