201254: [AtCoder]ARC125 E - Snack

Problem Statement

There are $N$ kinds of snacks numbered $1$ through $N$. We have $A_i$ pieces of Snack $i$.

There are $M$ children numbered $1$ through $M$. We will distribute the pieces of snacks to these children. Here, all of the following conditions must be satisfied.

• For every kind of snack, Child $i$ gets at most $B_i$ pieces of that kind.

• Child $i$ gets at most $C_i$ pieces of snacks in total.

Find the maximum total number of pieces of snacks that can be distributed to the children under these conditions.

Constraints

• $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}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 3
2 5 5
1 2 2
5 3 5

Sample Output 1

11

The optimal distribution of snacks is as follows.

• Child $1$ gets $1$, $1$, $1$ piece of Snacks $1$, $2$, $3$, respectively.

• Child $2$ gets $0$, $2$, $1$ piece(s) of Snacks $1$, $2$, $3$, respectively.

• Child $3$ gets $1$, $2$, $2$ piece(s) of Snacks $1$, $2$, $3$, respectively.

Sample Input 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

Sample Output 2

211