Задача D. Компьютерное зрение ≡

Условие

Ваша команда сейчас занимается разработкой нового робота. Вам поручена ответственная задача — научить робота находить на картинке ромбы.

Камера робота позволяет записывать черно-белые прямоугольные изображения шириной c и высотой r ячеек. Черная ячейка на изображении кодируется символом '#', а белая символом '@'. Ромбом называется связная область изображения, целиком состоящая из черных ячеек и удовлетворяющая следующим критериям:

• Ромб имеет какую-то целую высоту h ≥ 0.
• Ромб имеет центр, описываемый двумя координатами 1 ≤ x_c ≤ c, 1 ≤ y_c ≤ r. (x_c, y_c) — позиция ячейки на изображении.
• Все ячейки, имеющие координаты x, y, такие что |x−x_c| + |y−y_c| < h принадлежат ромбу и обязаны иметь черный цвет.

Например, вот корректные изображения ромбов имеющих высоту 2 (обратите внимание, что к ромбу могут прилегать и другие черные ячейки):

@@#@@ @###@ #####

@###@ ##### #####

@@#@@ @@#@@ #####

@@#@@ @###@ @@@@@

@#@#@ @@### @@@@@

@@#@@ @@#@@ @@@@@

Конечно, на одной картинке одновременно может находиться множество ромбов. Сейчас вам требуется найти максимальный из них по высоте.

Формат входных данных

В первой строке находятся два натуральных числа 1 ≤ r, c ≤ 1000 — высота и ширина изображения.

В следующих r строках находятся по c символов '@' или '#', означающих цвет ячеек изображения. '@' - белый цвет, '#' — черный цвет.

Формат выходных данных

Выведите одно целое число — максимальную высоту ромба на изображении. Если на изображении отсутствуют ромбы, то выведите 0.

Ограничения

1 ≤ r, c ≤ 10 — 40 баллов

1 ≤ r, c ≤ 100 — 20 баллов

1 ≤ r, c ≤ 1000 — 40 баллов

Примеры тестов

5 5
@@#@@
@###@
#####
@###@
@@#@@

3

3 5
@#@#@
#####
@#@#@

2

3 3
@@@
@@@
@@@

0