← 返回题目列表

AtCoder · awc0015_d

D. 烹饪任务的分配

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

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