E - Snack Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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

出力

答えを出力せよ．

入力例 1

3 3
2 5 5
1 2 2
5 3 5

出力例 1

11

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

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

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

  • 子供 3 は，お菓子 1,2,3 をそれぞれ 1,2,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

出力例 2

211

Score : 800 points

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