← 返回题目列表

AtCoder · abc308_f

I. 优惠券

中文机器翻译题面 查看原题

分数: 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