配点 : $800$ 点

問題文

$1$ から $N$ までの番号のついた $N$ 種類のお菓子があります． お菓子 $i$ は $A_i$ 個あります．

$1$ から $M$ までの番号のついた $M$ 人の子供がいます． この子供たちに，今からお菓子を配ります． ただし，お菓子を配る際には，次の条件を全て満たす必要があります．

• 子供 $i$ は，どの種類のお菓子も $B_i$ 個以下しかもらわない．
• 子供 $i$ がもらうお菓子の個数の合計は $C_i$ 以下である．

この条件のもとで，子どもたちに配るお菓子の個数の総和の最大値がいくらになるか求めてください．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^{12}$
• $1 \leq B_i \leq 10^7$
• $1 \leq C_i \leq 10^{12}$
• 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる．

$N$ $M$

$A_1$ $A_2$ $\cdots$ $A_N$

$B_1$ $B_2$ $\cdots$ $B_M$

$C_1$ $C_2$ $\cdots$ $C_M$

出力

答えを出力せよ．

3 3
2 5 5
1 2 2
5 3 5

11

次のようにお菓子を配ればよいです．

• 子供 $1$ は，お菓子 $1,2,3$ をそれぞれ $1,1,1$ 個もらう．
• 子供 $2$ は，お菓子 $1,2,3$ をそれぞれ $0,2,1$ 個もらう．
• 子供 $3$ は，お菓子 $1,2,3$ をそれぞれ $1,2,2$ 個もらう．

10 6
3 54 62 64 25 89 1 47 77 4
1 17 10 29 95 17
32 40 90 27 50 9

211