分数: 266 分
问题陈述
高桥在一家仓库担任运输经理。
该仓库管理 N 产品种类、产品初始库存数量 i (1 \leq i \leq N) is R_i 单位。
今天, M 运输请求按顺序到达。的 j-th (1 \leq j \leq M) 发货请求要求发货 S_j 产品单位 F_j.
Takahashi 按顺序处理请求 1-st 到 M-th。对于每个请求,他执行以下操作:
- 如果产品的当前库存数量 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
- 第一行包含一个整数 N 表示产品类型的数量和一个整数 M 代表运送请求的数量,以空格分隔。
- 第二行包含整数 R_1, R_2, \ldots, R_N 代表每种产品的初始库存数量,以空格分隔。
- 从 3-rd 行到 (2+M)第行,给出了每个运输请求的内容。
- 的 (2 + j)第行 (1 \leq j \leq M) 包含产品编号 F_j 中指定 j第次请求和发货数量 S_j,用空格分隔。
输出
在一行中输出成功发送的请求数。
示例输入 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