Vouchers

题目描述

你在商店里要购买 $N$ 件商品。第 $i$ 件商品的标价是 $P_i$ 日元（日本的货币）。 你有 $M$ 张优惠券。你可以使用第 $i$ 张优惠券以 $D_i$ 日元的折扣购买一件标价至少为 $L_i$ 日元的商品。 这里，每张优惠券只能使用一次。此外，同一件商品不能使用多张优惠券。 如果某件商品不使用优惠券，则按标价购买。 求购买所有 $N$ 件商品所需的最少总金额。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $P_1$ $\ldots$ $P_N$ $L_1$ $\ldots$ $L_M$ $D_1$ $\ldots$ $D_M$

输出格式

输出一个整数，表示答案。

3 3
4 3 1
4 4 2
2 3 1

4

10 5
9 7 1 5 2 2 5 5 7 6
7 2 7 8 2
3 2 4 1 2

37

提示

$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$ 所有输入值均为整数。考虑对第 $1$ 件商品使用第 $2$ 张优惠券，对第 $2$ 件商品使用第 $3$ 张优惠券。 那么，第 $1$ 件商品以 $4-3=1$ 日元购买，第 $2$ 件商品以 $3-1=2$ 日元购买，第 $3$ 件商品以 $1$ 日元购买。因此，购买所有商品共需 $1+2+1=4$ 日元。

标签: AtCoder|abc308F

来源

AtCoder|abc308F