Дистанционный практикум по программированию

Как известно, буква "О" − самая часто встречающаяся буква русского языка. Жители нашей области очень любят эту букву и даже установили ей памятник в центре Вологды.

Школьники Вася и Петя тоже любят букву "О". Как-то раз Петя взял клетчатый лист бумаги и нарисовал на нём несколько букв "О". Каждую букву он изобразил в виде прямоугольника. Ширина и высота каждого прямоугольника составляет не менее 3 клеток. Внутри прямоугольники пусты, толщина границы − одна клетка.

Вася посмотрел на рисунок Пети и задумался, какое максимальное количество прямоугольников могло быть нарисовано. Вася знает, что нарисованные прямоугольники могут касаться друг друга, пересекаться и даже быть один внутри другого. Однако, никакие два прямоугольника не совпадают полностью.

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

В первой строке входных данных вводится два разделённых пробелом числа M и N − размеры клетчатого листа. 3 ≤ M, N ≤ 250

Далее вводится M строк, каждая строка содержит N символов  '.' или '*', где символ '.' означает пустую клетку, а '*' - закрашенную.

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

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

Выведите одно число − максимально возможное количество прямоугольников, которое могло быть нарисовано.

Пример ввода 1 4 7 *****.. *..**** *****.* ...**** Пример вывода 1 4

Пример ввода 2 3 5 ***** ***** ***** Пример вывода 2 6

Пояснение к примеру 1.  На рисунке с помощью разного вида линий показаны 4 найденных прямоугольника.

Система оценивания. Решения, верно работающие при N, M ≤ 30, будут оцениваться из 30 баллов.  Решения, верно работающие при N, M ≤ 100, будут оцениваться из 75 баллов.