← 返回题目列表

AtCoder · awc0078_a

A. 仓库发货管理

中文机器翻译题面 查看原题

分数: 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