Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1 s 空间限制:256 MB

#13141. 拆除违建房屋

统计

题目描述

在城市的某个区域,有一批违建房屋需要拆除,而你负责调配拆迁队伍来完成这项任务。每栋违建房屋都有不同的坚固程度,就像有不同的“防御力”;每个拆迁队伍也有不同的拆除能力,如同具备不同的“攻击力”。

当一个拆迁队伍的拆除能力大于一栋违建房屋的坚固程度时,这栋违建房屋就会被成功拆除。一旦所有违建房屋都被拆除,剩下拆迁队伍的拆除能力就可以用来拆除周边一些附属的临时搭建物,即一个拆迁队伍只拆一栋建筑。

在实际操作中,合理安排拆迁队伍去拆除相应的违建房屋是非常关键的,你需要编写一个程序,计算出最多能完成多少额外的拆除工作(即最大“伤害”)。

输入格式

第一行输入两个整数 MN,其中 M 表示违建房屋的数量,N 表示拆迁队伍的数量。 接下来的 M 行,每行输入一个整数,代表每栋违建房屋的坚固程度。 再接下来的 N 行,每行输入一个整数,代表每个拆迁队伍的拆除能力。

输出格式

输出一行,为可以完成的额外拆除工作的最大值,也就是最多能造成的“伤害”。

输入样例

3 5 
1000 
2000 
1200 
2100 
2000 
1200 
1000 
1000

输出样例

2000

说明 / 提示

对于 80% 的数据,有 $1 \leq N, M \leq 1000$。 对于 100% 的数据,有 $1 \leq N, M \leq 100000$。

对样例的解释

这里有 3 栋违建房屋,坚固程度分别是 1000(a)、2000(b)、1200(c);有 5 个拆迁队伍,拆除能力分别为 2100(d)、2000(e)、1200(f)、1000(g)、1000(h)。最佳的安排是:拆迁队伍 d 去拆除房屋 b,队伍 e 拆除房屋 c,队伍 f 拆除房屋 a,而队伍 g 和 h 可以去拆除周边临时搭建物,它们拆除能力总和为 2000,所以最多能完成的额外拆除工作为 2000。