分数: 400 分
问题陈述
高桥是一家商店的经理 N 兼职工人。他需要完成 M 即将到来的假期有任务,并且必须准确分配 1 每项任务的兼职工人。
兼职工人编号为 1 to N,以及工人的技能水平 i is A_i。任务编号从 1 to M,以及任务所需的技能水平 j is D_j.
当工人 i 已分配给任务 j,他们的满意度计算为 A_i - D_j。由于如果员工的满意度为负,他们就会不满意,因此高桥希望进行一项分配,使每个分配的员工的满意度为 0 或更多(即没有人不满意)。
具体来说,他选择 M 工人出 N 兼职工人并分配选定的 M 工人到 M 任务一一对应。也就是说,让 f(j) 表示分配给任务的工作人员 j,他考虑一项作业 f 满足以下所有条件:
- 正是 1 兼职工人被分配到每项任务 j (1 \leq j \leq M).
- 不同的任务分配给不同的工人。也就是说,如果 j \neq j',然后 f(j) \neq f(j')。 (有些工人可能不会被分配到任何任务。)
- 对于分配给任务的每个工人,他们的满意度是 0 或更多。也就是说,对于每一个任务 j (1 \leq j \leq M), A_{f(j)} \geq D_j 成立。
如果存在满足这些条件的分配,则找到该分配的总满意度的最大值 M 分配的工人, \displaystyle\sum_{j=1}^{M}(A_{f(j)} - D_j)。如果不存在有效分配,则输出 -1.
约束
- 1 \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
- 所有输入值均为整数。
输入
N M A_1 A_2 \ldots A_N D_1 D_2 \ldots D_M
- 第一行包含一个整数 N 表示兼职工人的数量和一个整数 M 代表任务数量,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个工人的技能水平,以空格分隔。
- 第三行包含整数 D_1, D_2, \ldots, D_M 代表每个任务所需的技能级别,以空格分隔。
输出
如果存在有效分配,则在单行上以整数形式输出总满意度的最大值。如果不存在有效分配,则输出 -1 在一行上。
示例输入 1
4 3 5 3 7 1 2 4 6
示例输出 1
3
示例输入 2
3 3 1 2 3 4 5 6
示例输出 2
-1
示例输入 3
7 5 10 25 8 30 15 5 20 3 12 7 18 25
示例输出 3
35