落沙

• 时间限制：2 秒
• 内存限制：512 MiB

题目背景

这是本题的困难版本。本版本中，给定的需求量 (a_i) 不超过第 (i) 列原有的沙块数量。

题目描述

有一个 (n) 行 (m) 列的竖直棋盘。每个格子为空，或放有一块沙子。第 (i) 列底部有一个计数器，并给定非负整数 (a_i)。

一次操作可以扰动任意一块沙子。被扰动的沙块会从当前位置一直落到该列底部的计数器中。下落过程中，它会扰动与自己上下左右相邻的其他沙块；新被扰动的沙块也会按相同规则下落并继续扰动其他沙块。

当每一列的计数器中都至少有 (a_i) 块沙子时，谜题完成。

求完成谜题所需的最少操作次数。数据保证谜题有解。

输入格式

第一行包含两个正整数 (n,m)。

接下来 (n) 行，每行包含一个长度为 (m) 的字符串。其中 . 表示空格子，# 表示一块沙子。

最后一行包含 (m) 个非负整数 (a_1,a_2,\ldots,a_m)。

输出格式

输出一个非负整数，表示最少操作次数。

样例输入 1

5 7
#....#.
.#.#...
#....#.
#....##
#.#....
4 1 1 1 0 3 1

样例输出 1

3

样例输入 2

3 3
#.#
#..
##.
3 1 1

样例输出 2

1

样例输入 3

7 5
.#..#
#....
..##.
..##.
..###
..#..
#.##.
0 0 2 4 2

样例输出 3

1

样例解释

样例 1 的一种最优方案是扰动第一行第 (1) 列、第一行第 (6) 列以及第二行第 (4) 列的沙块。

样例 2 中，只需扰动第一行最右侧的沙块。

样例 3 中，只需扰动第一行最右侧的沙块。

数据范围

对所有数据：

• (1\le n\cdot m\le 400000)；
• (0\le a_i\le n)；
• (a_i) 不超过第 (i) 列原有的沙块数量。