分数: 500 点
问题陈述
您正在商店购买 N 项目。 正常价格为 i- 第一项是 P_i 日元(日本货币)。
你有 M 优惠券。 您可以使用 i第一张优惠券用于购买正常价格至少为 L_i 日元 D_i- 日元折扣。
这里,每张优惠券只能使用一次。 此外,多张优惠券不能用于同一商品。
如果某件商品没有使用优惠券,您将以正常价格购买。 求购买所有物品所需的最小可能总金额 N 项目。
约束
- 1\leq N,M\leq 2\times 10^5
- 1\leq P_i\leq 10^9
- 1\leq D_i \leq L_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M P_1 \ldots P_N L_1 \ldots L_M D_1 \ldots D_M
输出
将答案打印为整数。
示例输入 1
3 3 4 3 1 4 4 2 2 3 1
示例输出 1
4
考虑使用 2-nd 优惠券 1-st 项目,以及 3-rd 优惠券 2-第一项。
然后,您购买 1-st 项目 4-3=1 日元, 2-nd 项目 3-1=2 日元,以及 3-rd 项目 1 日元。 因此,您可以购买所有物品 1+2+1=4 日元。
示例输入 2
10 5 9 7 1 5 2 2 5 5 7 6 7 2 7 8 2 3 2 4 1 2
示例输出 2
37