F1. Падающий песок (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Разница в версиях заключается в ограничениях на $$$a_i$$$. Вы можете делать взломы, только если обе версии задачи решены.

Маленький Дорми недавно получил головоломку от своего друга, и ему требуется ваша помощь для ее решения.

Головоломка состоит из вертикальной доски с $$$n$$$ строками и $$$m$$$ столбцами, некоторые ячейки на доске пустые, а некоторые заполнены песком. Также даны $$$m$$$ неотрицательных целых чисел $$$a_1,a_2,\ldots,a_m$$$ ($$$0 \leq a_i \leq n$$$). В этой версии задачи $$$a_i$$$ равно числу ячеек с песком в столбце $$$i$$$.

Если стукнуть по ячейке, заполненной песком, то весь песок из ячейки упадет вниз на счетчик песка своего столбца (в каждом столбце есть счетчик песка). Когда песок падает, весь песок, в какой-либо момент находящийся в соседней ячейке с падающим песком, тоже начинает падать. А именно, если песок начинает падать из ячейки $$$(i,j)$$$, то он будет падать через все ячейки ниже в этом столбце, включая саму ячейку $$$(i,j)$$$, вызывая падения во всех ячейках, соседних к какой-либо ячейке на пути. Соседними к ячейке $$$(i,j)$$$ являются ячейки $$$(i-1,j)$$$, $$$(i,j-1)$$$, $$$(i+1,j)$$$ и $$$(i,j+1)$$$ (если такие существуют). Обратите внимание, что новые падающие ячейки песка тоже вызывают падение соседних ячеек.

За одну операцию вы можете стукнуть по одной ячейке с песком. Головоломка решена, если на счетчике песка в $$$i$$$-м столбце находится не менее $$$a_i$$$ ячеек с песком для всех столбцов от $$$1$$$ до $$$m$$$.

Вам нужно определить минимальное количество операций, необходимое, чтобы решить головоломку. Маленький Дорми никогда не даст вам головоломку, которую нельзя решить.

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

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

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

Последняя строка содержит $$$m$$$ неотрицательных целых чисел $$$a_1,a_2,\ldots,a_m$$$ ($$$0 \leq a_i \leq n$$$) — минимальное количество ячеек с песком, которые должны упасть на счетчик песка в каждом столбце. В этой версии задачи $$$a_i$$$ всегда равно количеству ячеек с песком в столбце $$$i$$$.

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

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

Примеры
Входные данные
5 7
#....#.
.#.#...
#....#.
#....##
#.#....
4 1 1 1 0 3 1
Выходные данные
3
Входные данные
3 3
#.#
#..
##.
3 1 1
Выходные данные
1
Примечание

В примере $$$1$$$ можно стукнуть ячейку в левом верхнем углу, ячейку во втором сверху ряду в четвертом столбце слева, и ячейку в третьем ряду сверху в шестом столбце слева. Тогда упадет необходимое количество песка в каждом столбце. Можно показать, что нельзя сделать меньше $$$3$$$ операций, и поэтому ответ равен $$$3$$$. Ниже приведен рисунок к первому примеру.

В примере $$$2$$$ можно стукнуть по ячейке в верхнем ряду в правом столбце, и весь песок в таблице упадет вниз. Поэтому ответ равен $$$1$$$. Ниже приведен рисунок ко второму примеру.