CF1534F2.Falling Sand (Hard Version)

This is the hard version of the problem. The difference between the versions is the constraints on $a_i$. You can make hacks only if all versions of the problem are solved.

Little Dormi has recently received a puzzle from his friend and needs your help to solve it.

The puzzle consists of an upright board with $n$ rows and $m$ columns of cells, some empty and some filled with blocks of sand, and $m$ non-negative integers $a_1,a_2,\ldots,a_m$ ($0 \leq a_i \leq n$). In this version of the problem, $a_i$ will always be not greater than the number of blocks of sand in column $i$.

When a cell filled with a block of sand is disturbed, the block of sand will fall from its cell to the sand counter at the bottom of the column (each column has a sand counter). While a block of sand is falling, other blocks of sand that are adjacent at any point to the falling block of sand will also be disturbed and start to fall. Specifically, a block of sand disturbed at a cell $(i,j)$ will pass through all cells below and including the cell $(i,j)$ within the column, disturbing all adjacent cells along the way. Here, the cells adjacent to a cell $(i,j)$ are defined as $(i-1,j)$, $(i,j-1)$, $(i+1,j)$, and $(i,j+1)$ (if they are within the grid). Note that the newly falling blocks can disturb other blocks.

In one operation you are able to disturb any piece of sand. The puzzle is solved when there are at least $a_i$ blocks of sand counted in the $i$-th sand counter for each column from $1$ to $m$.

You are now tasked with finding the minimum amount of operations in order to solve the puzzle. Note that Little Dormi will never give you a puzzle that is impossible to solve.

这是该问题的困难版本。两个版本的区别在于对 $a_i$ 的约束条件。只有当该问题的所有版本均被解决时，你才可以进行 hack。

小 Dormi 最近从朋友那里收到了一个谜题，需要你的帮助来解决它。

该谜题由一块竖直放置的板组成，板上有 $n$ 行 $m$ 列的格子，其中一些格子为空，另一些格子填有沙块；此外还给定 $m$ 个非负整数 $a_1,a_2,\ldots,a_m$（满足 $0 \leq a_i \leq n$）。在本版本中，$a_i$ 始终不超过第 $i$ 列中沙块的总数。

当一个填有沙块的格子被扰动时，该沙块将从其所在格子下落至该列底部的沙计数器中（每列均有一个沙计数器）。在沙块下落过程中，在任意时刻与该下落沙块相邻的其他沙块也会被扰动并开始下落。具体而言，位于格子 $(i,j)$ 处的沙块一旦被扰动，便会穿过该列中所有位于其下方（含自身）的格子，并在此过程中扰动所有途经的相邻格子。此处，格子 $(i,j)$ 的相邻格子定义为 $(i-1,j)$、$(i,j-1)$、$(i+1,j)$ 和 $(i,j+1)$（若它们位于网格范围内）。注意：新下落的沙块也可能扰动其他沙块。

每次操作中，你可以扰动任意一块沙块。当且仅当对于每一列 $i$（$i = 1, 2, \ldots, m$），第 $i$ 个沙计数器中统计到的沙块数量均不少于 $a_i$ 时，谜题即被解开。

你现在需要求出解开该谜题所需的最少操作次数。注意：小 Dormi 绝不会给你一个无解的谜题。

The first line consists of two space-separated positive integers $n$ and $m$ ($1 \leq n \cdot m \leq 400\,000$).

Each of the next $n$ lines contains $m$ characters, describing each row of the board. If a character on a line is '.', the corresponding cell is empty. If it is '#', the cell contains a block of sand.

The final line contains $m$ non-negative integers $a_1,a_2,\ldots,a_m$ ($0 \leq a_i \leq n$) — the minimum amount of blocks of sand that needs to fall below the board in each column. In this version of the problem, $a_i$ will always be not greater than the number of blocks of sand in column $i$.

第一行包含两个用空格分隔的正整数 $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$ 列中沙子块的总数。

Print one non-negative integer, the minimum amount of operations needed to solve the puzzle.

输出一个非负整数，表示解决该谜题所需的最少操作次数。

For example $1$, by disturbing both blocks of sand on the first row from the top at the first and sixth columns from the left, and the block of sand on the second row from the top and the fourth column from the left, it is possible to have all the required amounts of sand fall in each column. It can be proved that this is not possible with fewer than $3$ operations, and as such the answer is $3$. Here is the puzzle from the first example.

For example $2$, by disturbing the cell on the top row and rightmost column, one can cause all of the blocks of sand in the board to fall into the counters at the bottom. Thus, the answer is $1$. Here is the puzzle from the second example.

For example $3$, by disturbing the cell on the top row and rightmost column, it is possible to have all the required amounts of sand fall in each column. It can be proved that this is not possible with fewer than $1$ operation, and as such the answer is $1$. Here is the puzzle from the third example.

例如 $1$，通过扰动从上往下数第一行中从左往右数第 1 列和第 6 列的沙块，以及从上往下数第二行中从左往右数第 4 列的沙块，即可使每列落入底部计数器中的沙量恰好满足要求。可以证明，少于 $3$ 次操作无法达成目标，因此答案为 $3$。以下是第一个示例的谜题。

例如 $2$，通过扰动最顶行、最右列的格子，可使棋盘上所有沙块全部落入底部的计数器中。因此答案为 $1$。以下是第二个示例的谜题。

例如 $3$，通过扰动最顶行、最右列的格子，即可使每列落入底部计数器中的沙量恰好满足要求。可以证明，少于 $1$ 次操作无法达成目标，因此答案为 $1$。以下是第三个示例的谜题。