Это сложная версия задачи. Разница в версиях заключается в ограничениях на $$$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
7 5 .#..# #.... ..##. ..##. ..### ..#.. #.##. 0 0 2 4 2
1
В примере $$$1$$$ можно стукнуть по ячейке в левом верхнем углу, и по ячейке в третьей строке сверху в шестом столбце слева. Тогда на счетчики песка упадет необходимый объем песка в каждом столбце. Можно показать, что нельзя решить головоломку менее чем за $$$3$$$ операции, и поэтому ответ равен $$$3$$$. Ниже приведен рисунок к первому примеру.
В примере $$$2$$$ можно стукнуть по ячейке в верхнем ряду в правом столбце, и весь песок в таблице упадет вниз. Поэтому ответ равен $$$1$$$. Ниже приведен рисунок ко второму примеру.
В примере $$$3$$$ можно стукнуть по ячейке в верхнем ряду в правом столбце, и в каждом столбце упадет достаточно песка. Можно показать, что невозможно решить головоломку за менее, чем $$$1$$$ операцию, поэтому ответ $$$1$$$. Ниже приведен рисунок ко второму примеру.
