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

Кирпич  — прямоугольник с целыми сторонами шириной $$$1$$$ или высотой $$$1$$$ (или и то и другое).

Дана сетка $$$n\times m$$$, и каждая ячейка окрашена в черный или белый цвет. Замощение  — это способ поместить кирпичи на сетку так, чтобы каждая черная ячейка была покрыта ровно одним кирпичом, а каждая белая ячейка не была покрыта кирпичом. Другими словами, кирпичи размещаются только в черных ячейках, покрывают все черные ячейки, и никакие два кирпича не перекрываются.

Пример замощения с первого примера с использованием $$$5$$$ кирпичей. Существует также замощение из $$$4$$$ кирпичей.

Какое минимальное количество кирпичей необходимо для замощения данной сетки?

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

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

Следующие $$$n$$$ строки описывают сетку. $$$i$$$-я строка содержит строку длиной $$$m$$$, где $$$j$$$-я строка обозначает цвет ячейки в строке $$$i$$$, столбец $$$j$$$. Черная ячейка обозначается символом «#», а белая  — символом «.».

Гарантируется, что есть хотя бы одна черная ячейка.

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

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

Примеры
Входные данные
3 4
#.##
####
##..
Выходные данные
4
Входные данные
6 6
######
##....
######
##...#
##...#
######
Выходные данные
6
Входные данные
10 8
####..##
#..#.##.
#..#.###
####.#.#
....####
.###.###
###.#..#
########
###..###
.##.###.
Выходные данные
18
Примечание

Сетка с первого примера может быть замощена $$$4$$$-мя кирпичами, размещенными вертикально.

Сетка с третьего примера может быть замощена такими $$$18$$$ кирпичами: