A - 倉庫の出荷管理 解説 /

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

配点 : 266 点

問題文

高橋君は倉庫の出荷担当として働いています。

この倉庫には N 種類の商品が管理されており、商品 i (1 \leq i \leq N) の初期在庫数は R_i 個です。

今日は M 件の出荷依頼が順番に届きます。j 番目 (1 \leq j \leq M) の出荷依頼は、商品 F_j を S_j 個出荷してほしいという内容です。

高橋君は依頼を 1 番目から M 番目まで順に処理します。各依頼について、以下のように処理を行います。

  • 商品 F_j のその時点での在庫数が S_j 以上であれば、出荷に成功し、商品 F_j の在庫数を S_j 個減らします。
  • 商品 F_j のその時点での在庫数が S_j 未満であれば、出荷に失敗し、在庫数は変化しません。在庫がある分だけを出荷する（部分出荷する）ことはありません。また、失敗した依頼が後から再処理されることもありません。

すべての出荷依頼を処理し終えた後、出荷に成功した依頼の件数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq R_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq F_j \leq N (1 \leq j \leq M)
  • 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である。

入力

N M
R_1 R_2 \ldots R_N
F_1 S_1
F_2 S_2
\vdots
F_M S_M
  • 1 行目には、商品の種類数を表す整数 N と、出荷依頼の件数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各商品の初期在庫数を表す整数 R_1, R_2, \ldots, R_N が、スペース区切りで与えられる。
  • 3 行目から (2+M) 行目まで、各出荷依頼の内容が与えられる。
  • (2 + j) 行目 (1 \leq j \leq M) には、j 番目の依頼で指定された商品番号 F_j と、出荷数量 S_j が、スペース区切りで与えられる。

出力

出荷に成功した依頼の件数を 1 行で出力してください。

入力例 1

3 4
10 5 3
1 3
2 5
1 8
3 2

出力例 1

3

入力例 2

2 3
0 1
1 1
2 5
1 3

出力例 2

0

入力例 3

5 8
100 50 200 0 30
1 50
3 100
2 50
4 1
1 50
1 1
5 30
3 150

出力例 3

5

入力例 4

10 15
1000000000 500000000 0 100 999999999 1 1000000000 50 300 200
1 500000000
1 500000000
1 1
5 999999999
5 1
6 1
6 1
3 1
4 50
4 50
4 1
7 1000000000
8 25
8 25
10 200

出力例 4

10

入力例 5

1 1
0
1 1

出力例 5

0

Score : 266 pts

Problem Statement

Takahashi works as a shipping manager at a warehouse.

This warehouse manages N types of products, and the initial stock quantity of product i (1 \leq i \leq N) is R_i units.

Today, M shipping requests arrive in order. The j-th (1 \leq j \leq M) shipping request asks to ship S_j units of product F_j.

Takahashi processes the requests in order from the 1-st to the M-th. For each request, he performs the following:

  • If the current stock quantity of product F_j is at least S_j, the shipment succeeds, and the stock quantity of product F_j is decreased by S_j.
  • If the current stock quantity of product F_j is less than S_j, the shipment fails, and the stock quantity does not change. Partial shipment (shipping only the available amount) is not performed. Additionally, failed requests are never reprocessed later.

After all shipping requests have been processed, determine the number of requests that were successfully shipped.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 0 \leq R_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq F_j \leq N (1 \leq j \leq M)
  • 1 \leq S_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers.

Input

N M
R_1 R_2 \ldots R_N
F_1 S_1
F_2 S_2
\vdots
F_M S_M
  • The first line contains an integer N representing the number of product types and an integer M representing the number of shipping requests, separated by a space.
  • The second line contains integers R_1, R_2, \ldots, R_N representing the initial stock quantities of each product, separated by spaces.
  • From the 3-rd line to the (2+M)-th line, the contents of each shipping request are given.
  • The (2 + j)-th line (1 \leq j \leq M) contains the product number F_j specified in the j-th request and the shipping quantity S_j, separated by a space.

Output

Output the number of successfully shipped requests in a single line.

Sample Input 1

3 4
10 5 3
1 3
2 5
1 8
3 2

Sample Output 1

3

Sample Input 2

2 3
0 1
1 1
2 5
1 3

Sample Output 2

0

Sample Input 3

5 8
100 50 200 0 30
1 50
3 100
2 50
4 1
1 50
1 1
5 30
3 150

Sample Output 3

5

Sample Input 4

10 15
1000000000 500000000 0 100 999999999 1 1000000000 50 300 200
1 500000000
1 500000000
1 1
5 999999999
5 1
6 1
6 1
3 1
4 50
4 50
4 1
7 1000000000
8 25
8 25
10 200

Sample Output 4

10

Sample Input 5

1 1
0
1 1

Sample Output 5

0