← 返回题目列表

AtCoder · awc0027_d

D. 兼职工作轮班分配

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

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