题目描述

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

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

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

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

输入格式

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

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_M$ $C_1$ $C_2$ $\cdots$ $C_M$

输出格式

答えを出力せよ．

题目大意

有 $n$ 种零食 $m$ 个小孩。

每个小孩一种最多只能吃 $b_i$ 个，一共只能吃 $c_i$ 个。

把 $n$ 种零食依次喂给小孩，一共只有 $a_i$ 个 $i$ 种零食。

问所有小孩吃到零食数量的最大值。

3 3
2 5 5
1 2 2
5 3 5

11

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

提示

制約

• $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}$
• 入力される値はすべて整数である

Sample Explanation 1

次のようにお菓子を配ればよいです． - 子供 $1$ は，お菓子 $1,2,3$ をそれぞれ $1,1,1$ 個もらう． - 子供 $2$ は，お菓子 $1,2,3$ をそれぞれ $0,2,1$ 個もらう． - 子供 $3$ は，お菓子 $1,2,3$ をそれぞれ $1,2,2$ 個もらう．