分数: 400 分
问题陈述
高桥在兼职工作场所担任店长,负责轮班管理。
他需要为即将到来的工作制定轮班时间表 N 工作日。每个工作日都有编号 1, 2, \ldots, N和工作日 i (1 \leq i \leq N) 具有所需的技能水平 H_i 和预期销售额 S_i.
高桥的商店有 M 兼职工人,以及每个工人 j (1 \leq j \leq M) 具有技能等级 P_j。分配工人 j 至工作日 i,条件 必须满足 H_i \leq P_j 。换句话说,只有技能水平至少达到当天所需技能水平的工人才能被分配给它。
高桥想要分配所有 M 兼职工人以不同的工作日为准。自从 M \leq N,可能有一些工作日没有分配工作人员。具体来说,该作业必须满足以下所有条件:
- 每个工人都被准确地分配到 1 工作日。也就是说,所有 M 工人被分配到某个工作日,没有人未被分配。
- 最多 1 工作人员被分配到每个工作日。也就是说,没有一个工作日 2 或更多分配给它的工人。
- 如果工人 j 已分配给工作日 i,那么 H_i \leq P_j 必须保留。
仅在分配了工作人员的工作日获取预期销售额。也就是说,如果在某个任务中分配的工人的工作日集合是 T,那么 总销售额 该作业的 是 \displaystyle\sum_{i \in T} S_i.
确定是否可以以满足上述条件的方式分配所有工人。如果可能的话,找出所有有效分配中的最大总销售额。如果不可能,则输出 -1.
约束
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- 1 \leq S_i \leq 10^9
- 1 \leq P_j \leq 10^9
- 所有输入均为整数
- 的值 H_i, S_i, P_j 可能会重合,无论是在相同类型的变量之间还是在不同类型的变量之间
输入
N M H_1 S_1 H_2 S_2 \vdots H_N S_N P_1 P_2 \ldots P_M
- 第一行包含一个整数 N 表示工作日数和一个整数 M 代表兼职工人数量,以空格分隔。
- 以下 N 行,其中行 i (1 \leq i \leq N),包含所需的技能级别 H_i 和预期销售额 S_i 工作日 i,用空格分隔。
- 最后一行包含技能级别 P_1, P_2, \ldots, P_M ,用空格分隔。
输出
如果可以将所有工人分配到满足条件的不同工作日,则在一行中输出最大总销售额。如果不可能,则输出 -1.
示例输入 1
5 3 3 100 5 200 2 150 4 80 1 50 4 3 2
示例输出 1
330
示例输入 2
4 3 5 100 5 200 5 300 5 400 3 4 2
示例输出 2
-1
示例输入 3
8 5 10 500 7 300 15 800 5 200 12 600 3 100 8 450 20 1000 8 12 5 15 10
示例输出 3
2550