分数: 366 分
问题陈述
高桥是大学文化节上一个小吃摊的经理。 N 烹饪工作人员和 M 烹饪任务。
每个烹饪人员都有一个“技能等级”;的技能水平 i第一名工作人员是 A_i。同样,每个烹饪任务都有一个“所需的技能水平”; j- 第一个任务是 B_j.
仅当工作人员的技能水平至少达到任务所需的技能水平时,他们才能处理任务。换句话说, i第 名工作人员可以处理 j-第任务仅当 A_i \geq B_j.
Takahashi 以一对一的方式为工作人员分配任务。也就是说,每个工作人员最多可以被分配到 1 任务,每个任务最多可以分配给 1 工作人员。没有必要为每个工作人员分配任务,并且某些任务不分配工作人员也是可以接受的。
分配给工作人员的任务已完成,产生 1 菜结果。所有完成的菜肴均出售于 C 日元各。换句话说,如果 K 任务完成,销售总额为 K \times C 日元。
求高桥在最佳选择员工任务分配时可以获得的最大销售额。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq C \leq 10^9
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
- 所有输入均为整数
输入
N M C A_1 A_2 \ldots A_N B_1 B_2 \ldots B_M
- 第一行包含 N,工作人员人数, M,任务数量,以及 C,每道菜的售价,以空格分隔。
- 第二行包含每个工作人员的技能级别, A_1, A_2, \ldots, A_N,用空格分隔。
- 第三行包含每个任务所需的技能级别, B_1, B_2, \ldots, B_M,用空格分隔。
输出
打印高桥在一行中可以获得的最大销售额。注意,答案是一个不超过的非负整数 2 \times 10^{14}.
示例输入 1
3 3 500 5 3 1 2 4 6
示例输出 1
1000
示例输入 2
5 4 1000 10 3 7 1 8 5 2 9 4
示例输出 2
4000
示例输入 3
7 8 1000000000 100 50 80 30 60 90 10 20 40 60 80 100 55 35 75
示例输出 3
6000000000