分数: 400 分
问题陈述
高桥担任学园祭的执行委员会主席,并聘请了 N 兼职工作人员。每位工作人员 i (1 \leq i \leq N) 有工作效率 V_i,代表他们每小时可以完成的工作量。
学园祭当天, M 工作岗位已经出现。每份工作 j (1 \leq j \leq M) 有所需的工作量 D_j 和时间限制 T_j 完成时间。
高桥决定是否为每项工作分配一名工作人员。有些工作人员不分配任何工作是可以接受的,有些工作不分配人员而残缺不全也是可以接受的。但是,同一名工作人员不能被分配到多个工作岗位。也就是说,每个工作人员最多可以处理 1 工作。
当工作人员 i 已分配给作业 j,作业所需的时间为 D_j / V_i 小时。只有在要求的时间不超过时限的情况下,即只有当 D_j / V_i \leq T_j (相当于, V_i \times T_j \geq D_j)满意。不满足此条件的工作人员不能被分配到该工作。
确定高桥优化分配人员时可以完成的最大工作数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
- 1 \leq T_j \leq 10^9 (1 \leq j \leq M)
- 所有输入均为整数
输入
N M V_1 V_2 \ldots V_N D_1 T_1 D_2 T_2 \vdots D_M T_M
- 第一行包含 N,工作人员人数,以及 M,作业数,以空格分隔。
- 第二行包含工作效率 每个工作人员的 V_1, V_2, \ldots, V_N ,以空格分隔。
- 以下 M 行提供有关每个作业的信息。
- 的 (2 + j)- 第行包含所需的工作负载 D_j 和时间限制 T_j 的 j第一个作业,以空格分隔。
输出
在一行中输出可以完成的最大作业数。
示例输入 1
3 3 5 3 7 10 2 15 3 6 1
示例输出 1
2
示例输入 2
4 5 2 4 6 8 12 2 20 5 8 1 24 4 30 3
示例输出 2
3
示例输入 3
6 7 10 20 15 5 25 30 100 5 50 2 200 10 75 3 150 6 300 15 80 4
示例输出 3
3