Это простая версия задачи. Разница в версиях заключается в ограничениях на $$$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$$$. Ниже приведен рисунок ко второму примеру.
