A - 倉庫の在庫管理 解説 /

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

配点 : 266 点

問題文

高橋君は、N 個の倉庫を管理する物流センターの責任者です。各倉庫には保管できる容量の上限があります。

各倉庫 i（1 \leq i \leq N）には現在 W_i キログラムの荷物が保管されており、その倉庫の容量上限は L_i キログラムです。初期状態において W_i \leq L_i であるとは限らず、既に容量上限を超えている倉庫が存在する場合もあります。

これから M 回の荷物の搬入・搬出作業が順に行われます。j 回目（1 \leq j \leq M）の作業では、倉庫 P_j に対して C_j キログラムの荷物の変動が発生します。C_j が正の場合は搬入（荷物が増加）、C_j が負の場合は搬出（荷物が減少）、C_j = 0 の場合は変動なしを意味します。同じ倉庫に対して複数回の作業が行われることもあります。

作業の途中や終了後に、倉庫の荷物の量が容量上限を超えたり負の値になったりしても、作業は中断されずそのまま続行されます。最終的な荷物の量が負になる場合も、そのまま通常通り容量超過の判定を行います。

すべての作業が終了した後に、容量超過となっている倉庫の個数を求めてください。倉庫 i が容量超過であるとは、倉庫 i の最終的な荷物の量が L_i より真に大きいことを指します（L_i と等しい場合は容量超過ではありません）。判定は、すべての作業終了後の最終的な荷物の量のみに基づいて行います。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq W_i \leq 10^9
  • 1 \leq L_i \leq 10^9
  • W_i > L_i である場合もある
  • 1 \leq P_j \leq N
  • -10^9 \leq C_j \leq 10^9（C_j = 0 の場合もある）
  • 入力はすべて整数

入力

N M
W_1 L_1
W_2 L_2
\vdots
W_N L_N
P_1 C_1
P_2 C_2
\vdots
P_M C_M
  • 1 行目には、倉庫の個数を表す整数 N と、作業の回数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各倉庫の情報が与えられる。
  • 1 + i 行目では、倉庫 i の現在の荷物量 W_i と容量上限 L_i が、スペース区切りで与えられる。
  • N + 2 行目から N + M + 1 行目では、各作業の情報が与えられる（M = 0 の場合、この部分は存在しない）。
  • N + 1 + j 行目では、j 回目の作業対象の倉庫番号 P_j と、荷物の変動量 C_j が、スペース区切りで与えられる。

出力

すべての作業終了後に容量超過となっている倉庫の個数を 1 行で出力せよ。

入力例 1

3 4
50 100
80 100
30 50
1 30
2 25
3 15
2 10

出力例 1

1

入力例 2

5 6
100 200
150 150
0 100
200 300
50 80
2 10
3 50
5 20
1 150
3 60
5 15

出力例 2

4

入力例 3

10 12
500000000 1000000000
999999999 1000000000
0 100
750000000 800000000
100 100
0 1000000000
123456789 500000000
999999998 999999999
50 50
1000000000 1000000000
1 500000001
2 2
4 100000000
5 1
9 1
7 400000000
3 -50
8 5
6 1000000000
10 1
3 200
4 -50000000

出力例 3

8

Score : 266 pts

Problem Statement

Takahashi is the manager of a logistics center that oversees N warehouses. Each warehouse has an upper limit on its storage capacity.

Each warehouse i (1 \leq i \leq N) currently stores W_i kilograms of goods, and its capacity limit is L_i kilograms. It is not necessarily the case that W_i \leq L_i in the initial state; there may be warehouses that already exceed their capacity limit.

A total of M loading/unloading operations will be performed in order. In the j-th operation (1 \leq j \leq M), a change of C_j kilograms occurs at warehouse P_j. If C_j is positive, it represents loading (goods increase); if C_j is negative, it represents unloading (goods decrease); if C_j = 0, it means no change. Multiple operations may be performed on the same warehouse.

Even if the amount of goods in a warehouse exceeds its capacity limit or becomes negative during or after the operations, the operations continue without interruption. Even if the final amount of goods is negative, the overcapacity check is performed as usual.

After all operations are completed, determine the number of warehouses that are over capacity. Warehouse i is over capacity if the final amount of goods in warehouse i is strictly greater than L_i (if it equals L_i, it is not over capacity). The determination is based solely on the final amount of goods after all operations are completed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq W_i \leq 10^9
  • 1 \leq L_i \leq 10^9
  • It is possible that W_i > L_i
  • 1 \leq P_j \leq N
  • -10^9 \leq C_j \leq 10^9 (including the case C_j = 0)
  • All input values are integers

Input

N M
W_1 L_1
W_2 L_2
\vdots
W_N L_N
P_1 C_1
P_2 C_2
\vdots
P_M C_M
  • The first line contains two space-separated integers: N, the number of warehouses, and M, the number of operations.
  • Lines 2 through N + 1 give the information for each warehouse.
  • Line 1 + i contains the current amount of goods W_i and the capacity limit L_i of warehouse i, separated by a space.
  • Lines N + 2 through N + M + 1 give the information for each operation (this part does not exist if M = 0).
  • Line N + 1 + j contains the target warehouse number P_j and the change in goods C_j for the j-th operation, separated by a space.

Output

Print the number of warehouses that are over capacity after all operations are completed, on a single line.

Sample Input 1

3 4
50 100
80 100
30 50
1 30
2 25
3 15
2 10

Sample Output 1

1

Sample Input 2

5 6
100 200
150 150
0 100
200 300
50 80
2 10
3 50
5 20
1 150
3 60
5 15

Sample Output 2

4

Sample Input 3

10 12
500000000 1000000000
999999999 1000000000
0 100
750000000 800000000
100 100
0 1000000000
123456789 500000000
999999998 999999999
50 50
1000000000 1000000000
1 500000001
2 2
4 100000000
5 1
9 1
7 400000000
3 -50
8 5
6 1000000000
10 1
3 200
4 -50000000

Sample Output 3

8