题目思路

由于优惠券只能选一个，所以肯定选择需要购买数量最少的，然后选择最大那几个作为优惠券使用的目标，这样就可以让减免的书籍的价格最大化。

时间复杂度$O(n)$

代码

Java

问题描述

小红在商店中选购了 $n$ 件商品，每件商品的价格分别为 $P_1, P_2, ..., P_n$。商店提供了 $m$ 张优惠券，每张优惠券对应可以减免特定数量商品中价格最低者的金额。每张优惠券标注了一个数字 $a_i$，表示使用该优惠券时需选购恰好 $a_i$ 件商品进行折扣。小红只能使用一张优惠券，求小红如何选择使用优惠券以使得总花费最小。

输入格式

第一行包含两个正整数 $n, m$，分别表示商品的数量和优惠券的数量。
第二行包含 $n$ 个空格分隔的正整数 $P_1, P_2, ..., P_n$，表示每件商品的价格。
第三行包含 $m$ 个空格分隔的正整数 $a_1, a_2, ..., a_m$，表示每张优惠券对应的商品数量。

输出格式

输出一行一个整数，表示小红使用优惠券后的最小总花费。

样例输入

3 2
90 30 40
2 3

样例输出

120

评测数据与规模

对于所有评测数据，满足 $1 < n, m < 50000$，$1 \le a_i \le n$，$1 \le P_i \le 10^4$。