Сон пастуха

Limits: 4 sec., 512 MiB

Зеник пішов на поле пасти своїх жеребців. Поле має форму прямокутника та поділене на \(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)\) — це максимальна гучність, з якою чутно коней на цій ділянці. Якщо на ділянці не чутно жодного коня, то рівень шуму дорівнює нулю.

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

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

Input

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

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

Output

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

Constraints

\(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 балів: без додаткових обмежень.

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

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

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

• Коня розміром \(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\).