Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. Хоссам и буква
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Хоссам купил новый участок земли длины $$$n$$$ и ширины $$$m$$$, он поделил его на $$$n \cdot m$$$ квадратов, каждый из которых имеет размер $$$1\times1$$$.

Так как имя Хоссам начинается с латинской буквы 'H', он хочет нарисовать большую букву 'H' путем построения стен размера $$$1\times1$$$ на некоторых квадратах земли. Каждый квадрат земли $$$1\times1$$$ может быть одного из трех типов: идеальный, средний, или плохой.

Процесс возведения стен для формирования буквы 'H' имеет следующие ограничения:

  • Буква должна состоять из одной горизонтальной и двух вертикальных линий.
  • Вертикальные линии не должны находиться в одном и том же или соседних столбцах.
  • Вертикальные линии должны начинаться в одной строке и заканчиваться в одной строке (и, следовательно, иметь одинаковую длину).
  • Горизонтальная линия должна соединять вертикальные линии, но не должна пересекать их.
  • Горизонтальная линия может находиться в любом ряду между вертикальными линиями (не только в середине), кроме верхней и нижней. (С горизонтальной линией в верхнем ряду буква выглядит как 'n', а в нижнем ряду как 'U'.)
  • Запрещается возводить стены в квадратах плохого качества.
  • Вы можете использовать не более одного квадрата среднего качества.
  • Вы можете использовать любое количество квадратов идеального качества.

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

Смотрите примечание для получения дополнительных разъяснений.

Входные данные

Первая строка ввода содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \le n, m \le 400$$$).

Следующие $$$n$$$ строк содержат $$$m$$$ символов, описывающих участок. Символ '.' кодирует квадрат превосходного качества, 'm' — среднего качества, '#' — плохого качества.

Выходные данные

Выведите одно целое число — максимальное число стен в букве 'H'.

Если никак не возможно написать букву 'H', выведите $$$0$$$.

Примеры
Входные данные
2 3
#m.
.#.
Выходные данные
0
Входные данные
7 8
...#.m..
..m...m.
.#..#.m#
...m..m.
m.......
..#.m.mm
......m.
Выходные данные
16
Примечание

В первом тестовом примере никак не возможно написать букву 'H'.

Во втором примере, картинка показывает участок и некоторые допустимые буквы 'H'. Идеальные, средние, и плохие квадраты выделены белым, желтым, и черным цветом соответственно.