B - 工場の受注処理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は工場の生産管理を担当しています。この工場では、ある製品を生産しています。

製品 1 個を作るには、M 種類の部品がそれぞれ 1 個ずつ必要です。j 番目の部品の在庫は最初 B_j 個あります。

今日、N 件の注文を i = 1, 2, \ldots, N の順に処理します。i 番目の注文では、製品をちょうど A_i 個納品する必要があります。

i 番目の注文を処理するとき、その時点での在庫がすべての種類の部品について A_i 個以上であれば、製品を A_i 個生産して納品します。このとき、すべての種類の部品の在庫がそれぞれ A_i 個減ります。いずれか 1 種類でも在庫が A_i 個未満であれば、その注文はキャンセルとなり、製品を 1 個も生産せず、部品の在庫も変化しません。

すべての注文を処理した後、実際に納品できた注文の件数を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq M \leq 5 \times 10^5
  • N + M \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_j \leq 10^9
  • 入力はすべて整数である。

入力

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • 1 行目には、注文の件数 N と部品の種類数 M が、スペース区切りで与えられる。
  • 2 行目には、各注文で納品すべき製品数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各部品の初期在庫数 B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。

出力

実際に納品できた注文の件数を 1 行で出力せよ。

入力例 1

4 3
2 1 3 1
5 4 6

出力例 1

3

入力例 2

5 2
4 2 3 1 2
3 5

出力例 2

2

入力例 3

8 6
5 7 4 6 3 2 8 1
20 17 23 19 18 21

出力例 3

4

入力例 4

20 15
8 7 10 6 5 9 4 3 12 2 11 1 13 5 4 7 6 2 8 3
60 55 58 62 57 59 61 56 63 54 64 65 66 53 67

出力例 4

9

入力例 5

1 1
1000000000
1000000000

出力例 5

1

Score : 300 pts

Problem Statement

Takahashi is in charge of production management at a factory. This factory produces a certain product.

To make 1 unit of the product, exactly 1 of each of M types of parts is required. The initial stock of the j-th part is B_j units.

Today, N orders are processed in the order i = 1, 2, \ldots, N. The i-th order requires delivering exactly A_i units of the product.

When processing the i-th order, if the current stock of every type of part is at least A_i, then A_i units of the product are produced and delivered. In this case, the stock of every type of part decreases by A_i. If even one type of part has stock less than A_i, the order is cancelled — no products are produced and the part stocks do not change.

After all orders have been processed, determine the number of orders that were actually delivered.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq M \leq 5 \times 10^5
  • N + M \leq 5 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_j \leq 10^9
  • All input values are integers.

Input

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • The first line contains the number of orders N and the number of part types M, separated by a space.
  • The second line contains the number of products to deliver for each order A_1, A_2, \ldots, A_N, separated by spaces.
  • The third line contains the initial stock of each part B_1, B_2, \ldots, B_M, separated by spaces.

Output

Print the number of orders that were actually delivered, on a single line.

Sample Input 1

4 3
2 1 3 1
5 4 6

Sample Output 1

3

Sample Input 2

5 2
4 2 3 1 2
3 5

Sample Output 2

2

Sample Input 3

8 6
5 7 4 6 3 2 8 1
20 17 23 19 18 21

Sample Output 3

4

Sample Input 4

20 15
8 7 10 6 5 9 4 3 12 2 11 1 13 5 4 7 6 2 8 3
60 55 58 62 57 59 61 56 63 54 64 65 66 53 67

Sample Output 4

9

Sample Input 5

1 1
1000000000
1000000000

Sample Output 5

1