A - Parking Lot Full Check Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は大型ショッピングモールの駐車場管理システムを担当しています。このショッピングモールには N 個の駐車場エリアがあり、各エリア i (1 \leq i \leq N) には S_i 台分の駐車スペースがあります。開店時点ではすべての駐車スペースが空いています。

開店から閉店までの間に M 件の駐車リクエストが届きます。各駐車リクエスト j (1 \leq j \leq M) は、駐車場エリア番号 T_j と駐車を希望する台数 P_j の組で表されます。ここで、車 1 台は駐車スペース 1 台分を使用します。駐車リクエストは j = 1, 2, \ldots, M の順に 1 件ずつ処理され、以下のルールに従います。

  • 指定されたエリア T_j の現在の空きスペース数が P_j 以上であれば、駐車は成功し、そのエリアの空きスペース数が P_j だけ減少する。
  • 指定されたエリア T_j の現在の空きスペース数が P_j 未満であれば、駐車は失敗する。この場合、一部の台数だけを駐車させることはできず、P_j 台すべてが駐車できずに去る。そのエリアの空きスペース数は変化しない。

なお、開店から閉店までの間に車が出庫することはなく、空きスペース数が増えることはありません。

すべての駐車リクエストを処理した後、満車であるエリアの個数を求めてください。ここで、あるエリアが満車であるとは、そのエリアの空きスペース数が 0 であることを意味します。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq M)
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数である。

入力

N M
S_1 S_2 \ldots S_N
T_1 P_1
T_2 P_2
\vdots
T_M P_M
  • 1 行目には、駐車場エリアの数を表す N と、駐車リクエストの数を表す M が、空白区切りで与えられる。
  • 2 行目には、各エリアの駐車スペースの総数を表す S_1, S_2, \ldots, S_N が、空白区切りで与えられる。
  • 続く M 行にわたって、駐車リクエストの情報が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) には、j 番目の駐車リクエストのエリア番号 T_j と駐車を希望する台数 P_j が、空白区切りで与えられる。

出力

すべての駐車リクエストを処理した後、満車（空きスペース数が 0）であるエリアの個数を 1 行で出力せよ。

入力例 1

3 5
10 5 3
1 4
2 3
1 6
2 2
3 3

出力例 1

3

入力例 2

5 8
100 3 50 1 20
1 40
2 2
3 25
4 1
2 1
1 60
3 30
2 5

出力例 2

3

入力例 3

7 12
1000000000 500 8 1000000000 15 100 999999999
1 500000000
1 500000000
3 5
5 10
3 3
5 5
2 501
4 999999999
6 50
3 1
4 1
6 60

出力例 3

4

Score : 266 pts

Problem Statement

Takahashi is in charge of the parking lot management system for a large shopping mall. This shopping mall has N parking areas, and each area i (1 \leq i \leq N) has S_i parking spaces. At the time of opening, all parking spaces are empty.

Between opening and closing, M parking requests arrive. Each parking request j (1 \leq j \leq M) is represented by a pair of the parking area number T_j and the number of cars P_j that wish to park. Here, one car uses one parking space. The parking requests are processed one at a time in the order j = 1, 2, \ldots, M, following these rules:

  • If the current number of available spaces in the specified area T_j is at least P_j, the parking succeeds, and the number of available spaces in that area decreases by P_j.
  • If the current number of available spaces in the specified area T_j is less than P_j, the parking fails. In this case, it is not possible to park only a partial number of cars; all P_j cars leave without parking. The number of available spaces in that area does not change.

Note that no cars leave the parking lot between opening and closing, so the number of available spaces never increases.

After processing all parking requests, find the number of areas that are full. Here, an area is full means that the number of available spaces in that area is 0.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq T_j \leq N (1 \leq j \leq M)
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers.

Input

N M
S_1 S_2 \ldots S_N
T_1 P_1
T_2 P_2
\vdots
T_M P_M
  • The first line contains N, the number of parking areas, and M, the number of parking requests, separated by a space.
  • The second line contains S_1, S_2, \ldots, S_N, the total number of parking spaces in each area, separated by spaces.
  • The following M lines contain the parking request information.
  • The (2 + j)-th line (1 \leq j \leq M) contains the area number T_j and the desired number of cars P_j for the j-th parking request, separated by a space.

Output

After processing all parking requests, output in one line the number of areas that are full (i.e., have 0 available spaces).

Sample Input 1

3 5
10 5 3
1 4
2 3
1 6
2 2
3 3

Sample Output 1

3

Sample Input 2

5 8
100 3 50 1 20
1 40
2 2
3 25
4 1
2 1
1 60
3 30
2 5

Sample Output 2

3

Sample Input 3

7 12
1000000000 500 8 1000000000 15 100 999999999
1 500000000
1 500000000
3 5
5 10
3 3
5 5
2 501
4 999999999
6 50
3 1
4 1
6 60

Sample Output 3

4