优惠券

题目描述

你在一家商店要买 $N$ 件商品。第 $i$ 件商品的正常价格为 $P_i$ 日元(日元是日本的货币单位)。

你有 $M$ 张优惠券。使用第 $i$ 张优惠券购买正常价格至少为 $L_i$ 日元的商品时,可以享受 $D_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

考虑对第 $1$ 件商品使用第 $2$ 张优惠券,对第 $2$ 件商品使用第 $3$ 张优惠券。

此时,第 $1$ 件商品以 $4-3=1$ 日元购买,第 $2$ 件商品以 $3-1=2$ 日元购买,第 $3$ 件商品以 $1$ 日元购买。因此,可以以 $1+2+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 \le N,M \le 2\times 10^5$
• $1 \le P_i \le 10^9$
• $1 \le D_i \le L_i \le 10^9$
• 输入中的所有值均为整数