問題文

あなたは店で $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$ 個目の商品に使うことを考えます。

このとき、$1$ 個目の商品を $4-3=1$ 円、$2$ 個目の商品を $3-1=2$ 円、$3$ 個目の商品を $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