U736575 F - 芙兰)(达
题目背景
没想到芙兰达连鬼畜起来都那么地萌啊,好想抱一只回家www~。
PS:小天使你又有新的小伙伴了哦,还是个萌妹纸!逆输出 sm21264834
题目描述
商店里有 $n$ 个炸弹,第 $i$ 个炸弹的价格为 $a_i$。
芙兰达准备购买全部炸弹。
商店提供了 $m$ 张优惠券,第 $i$ 张优惠券上写着一个整数 $k_i$。
使用第 $i$ 张优惠券时,需要选择 $k_i$ 个还没有被其他优惠券选择过的炸弹。
在这 $k_i$ 个炸弹中,价格最低的炸弹可以免费获得,其余炸弹需要正常支付价格。
也就是说,如果选择的炸弹价格为:
$$
b_1,b_2,\dots,b_{k_i}
$$
那么需要支付:
$$
\sum_{j=1}^{k_i} b_j-\min(b_1,b_2,\dots,b_{k_i})
$$
的费用。
每张优惠券最多使用一次,并且不同优惠券之间选择的炸弹不能重复。
请你帮助芙兰达决定如何使用优惠券,使购买全部炸弹所需要支付的钱最少。
输入格式
第一行输入两个整数 $n,m$,分别表示炸弹数量和优惠券数量。
第二行输入 $n$ 个整数:
$$
a_1,a_2,\dots,a_n
$$
表示每个炸弹的价格。
第三行输入 $m$ 个整数:
$$
k_1,k_2,\dots,k_m
$$
表示每张优惠券可以选择的炸弹数量。
输出格式
输出一个整数,表示使用优惠券后购买全部炸弹的最少花费。
说明/提示
#### **样例解释**
共有 $5$ 个炸弹,价格分别为:
```text
5 4 3 2 1
```
共有两张优惠券:
- 第一张优惠券可以选择 $2$ 个炸弹;
- 第二张优惠券可以选择 $3$ 个炸弹。
一种最优方案:
第一张优惠券选择:
$$
5,4
$$
其中价格最低的 $4$ 免费,需要支付:
$$
5
$$
第二张优惠券选择:
$$
3,2,1
$$
其中价格最低的 $1$ 免费,需要支付:
$$
3+2=5
$$
最终需要支付:
$$
5+5=10
$$
#### **数据范围**
对于所有测试数据,保证:
$$
1\le n,m\le2\times10^5
$$
$$
1\le a_i\le10^9
$$
$$
1\le k_i\le n
$$
详细的子任务限制如下:
| 子任务 | 分值 | 特殊性质 |
| :--: | :--: | :-- |
| 1 | 50 分 | $n,m\le100$ |
| 2 | 50 分 | 无特殊限制 |