这是问题的简单版本。版本之间的差异在于 $$$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)$$$(如果它们在网格内)。请注意,新落下的方块可能会干扰其他方块。
在一次操作中,您可以扰动任何一块沙子。当从 $$$1$$$ 到 $$$m$$$ 的每一列的第 $$$i$$$ 沙子计数器中至少有 $$$a_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$$$ 列中沙块的数量。
输出
打印一个非负整数,即解决该难题所需的最少运算量。
示例
输入 #1
5 7 #....#. .#.#... #....#. #....## #.#.... 4 1 1 1 0 3 1
输出 #1
3
输入 #2
3 3 #.# #.. ##. 3 1 1
输出 #2
1
注意
例如$$$1$$$,通过扰动从左起第一行和左起第六列的沙块,以及从顶部起第二行和左起第四列的沙块,可以让每列中落下所有所需数量的沙子。可以证明,少于 $$$3$$$ 操作是不可能的,因此答案是 $$$3$$$。这是第一个示例中的谜题。
例如$$$2$$$,通过干扰顶行和最右列的单元格,可以导致棋盘中的所有沙块落入底部的柜台中。因此,答案是$$$1$$$。这是第二个例子中的谜题。