题目描述

你正在一家商店购买 $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$ 张优惠券用于第 $1$ 件商品，将第 $3$ 张优惠券用于第 $2$ 件商品。

然后，你以 $4-3=1$ 日元购买第 $1$ 件商品，以 $3-1=2$ 日元购买第 $2$ 件商品，以及以 $1$ 日元购买第 $3$ 件商品。因此，你可以以 $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