← 返回题目列表

AtCoder · awc0032_d

D. 兼职工作轮班分配

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

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