题目描述

你打算在商店里购买 $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

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$ 张优惠券用于第 $1$ 件商品，将第 $3$ 张优惠券用于第 $2$ 件商品。

此时，第 $1$ 件商品的价格为 $4 - 3 = 1$ 日元，第 $2$ 件商品的价格为 $3 - 1 = 2$ 日元，第 $3$ 件商品未使用优惠券，按原价 $1$ 日元购买。

因此，购买所有商品的总费用为 $1 + 2 + 1 = 4$ 日元。