Кирпич — прямоугольник с целыми сторонами шириной \(1\) или высотой \(1\) (или и то и другое).
Дана сетка \(n\times m\), и каждая ячейка окрашена в черный или белый цвет. Замощение — это способ поместить кирпичи на сетку так, чтобы каждая черная ячейка была покрыта ровно одним кирпичом, а каждая белая ячейка не была покрыта кирпичом. Другими словами, кирпичи размещаются только в черных ячейках, покрывают все черные ячейки, и никакие два кирпича не перекрываются.
Какое минимальное количество кирпичей необходимо для замощения данной сетки?
Первая строка содержит два целых числа \(n\), \(m\) (\(1\le n, m\le 200\)) — количество строк и столбцов соответственно.
Следующие \(n\) строки описывают сетку. \(i\)-я строка содержит строку длиной \(m\), где \(j\)-я строка обозначает цвет ячейки в строке \(i\), столбец \(j\). Черная ячейка обозначается символом «#», а белая — символом «.».
Гарантируется, что есть хотя бы одна черная ячейка.
Выведите единственное целое число — минимальное количество требуемых кирпичей.
Сетка с первого примера может быть замощена \(4\)-мя кирпичами, размещенными вертикально.
Сетка с третьего примера может быть замощена такими \(18\) кирпичами:
3 4 #.## #### ##..
4
6 6 ###### ##.... ###### ##...# ##...# ######
6
10 8 ####..## #..#.##. #..#.### ####.#.# ....#### .###.### ###.#..# ######## ###..### .##.###.
18
4000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач