#522. 「多校联考 Round 2」落沙成塔

内存限制:512 MiB 时间限制:2000 ms 输入文件:sand.in 输出文件:sand.out
题目类型:传统 评测方式:文本比较
上传者: std

题目描述

小D非常喜欢Minecraft,他今天在Minecraft中建水晶宫殿,这需要非常多的沙子。众所周知,Minecraft中不稳定沙子具有受到扰动就会下落的性质,于是小D于是决定在一片不稳定沙漠中收集沙子,然而跑来跑去很麻烦,小D想最小化自己手动扰动次数。但是小D实在太菜了,自己算不出来,只好请您帮忙了。值得注意注意的是,由于小D是只二维生物,他玩的Minecraft也是二维的。

具体来说,给你一个 n m 列的网格和一个长度为 m 的序列 a 。每个位置要么是空的,要么有一块沙子。保证 a_i 的值小于等于网格第 ii 列的沙子块数。

你可以选择任意一块仍然在网格中的沙子并“干扰”这块沙子。当一块沙子被“干扰”后,它会从当前位置竖直下落,并最终掉出网格。另外,所有与一块下落的沙子经过的任意位置相邻的沙子也会开始竖直下落,任意下落的沙子都会使相邻的沙子下落(如果这一段看不懂,可以阅读样例,样例中用黑色方框标记的是被“干扰”的沙子,用叉标记的是自动下落的沙子)。

你的目标是使第 i 列至少有 a_i 块沙子掉出网格。

求你最少需要“干扰”多少块沙子。

网格由字符 . 和字符 # 构成,. 表示这个位置是空的,# 表示这个位置有一块沙子。

输入格式

sand.in 中读入。

一行两个整数 n,m 意义如题目所述

接下来一个 n m 列的二维表格。

最后一行 m 个整数,表示每一行最小需要落下来的沙子数量。

输出格式

输出到 sand.out 中。

一行一个整数,表示最少需要扰动的沙子数量。

样例

见附加文件的 sample1.in/ans sample2.in/ans

样例解释

样例解释

数据范围与提示

编号 n \le m \le 特殊性质
1~4 10
5~8 100
9~12 300
13~15 650
16~20

特殊性质: \forall 1 \le i \le m ,a_i = c_i 其中 c_i 为第i列拥有的沙子总数。