D - Assignment of Cooking Tasks Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は大学の学園祭で模擬店の運営責任者を務めています。彼は N 人の調理担当スタッフと M 個の調理タスクを管理しています。

各調理担当スタッフには「スキルレベル」が設定されており、i 番目のスタッフのスキルレベルは A_i です。同様に、各調理タスクには「必要スキルレベル」が設定されており、j 番目のタスクの必要スキルレベルは B_j です。

スタッフがタスクを担当できるのは、そのスタッフのスキルレベルがタスクの必要スキルレベル以上である場合に限ります。つまり、i 番目のスタッフが j 番目のタスクを担当できるのは A_i \geq B_j のときに限ります。

高橋君は、スタッフとタスクの間で1対1の割り当てを行います。すなわち、各スタッフには最大 1 つのタスクを割り当てることができ、各タスクには最大 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
  • 1 行目には、スタッフの人数を表す N 、タスクの個数を表す M 、料理 1 品あたりの販売価格を表す C が、スペース区切りで与えられる。
  • 2 行目には、各スタッフのスキルレベルを表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各タスクの必要スキルレベルを表す B_1, B_2, \ldots, B_M が、スペース区切りで与えられる。

出力

高橋君が得られる最大の売上金額を 1 行で出力してください。なお、答えは 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

Score : 366 pts

Problem Statement

Takahashi is the manager of a food stall at his university's school festival. He manages N cooking staff members and M cooking tasks.

Each cooking staff member has a "skill level"; the skill level of the i-th staff member is A_i. Similarly, each cooking task has a "required skill level"; the required skill level of the j-th task is B_j.

A staff member can handle a task only if their skill level is at least the required skill level of the task. In other words, the i-th staff member can handle the j-th task only when A_i \geq B_j.

Takahashi assigns staff members to tasks in a one-to-one manner. That is, each staff member can be assigned to at most 1 task, and each task can be assigned to at most 1 staff member. It is not necessary to assign a task to every staff member, and it is acceptable for some tasks to have no staff member assigned to them.

A task to which a staff member is assigned is completed, producing 1 dish as a result. All completed dishes are sold at C yen each. In other words, if K tasks are completed, the total sales amount is K \times C yen.

Find the maximum sales amount Takahashi can obtain when he optimally chooses the assignment of staff members to tasks.

Constraints

  • 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)
  • All inputs are integers

Input

N M C
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_M
  • The first line contains N, the number of staff members, M, the number of tasks, and C, the selling price per dish, separated by spaces.
  • The second line contains the skill levels of each staff member, A_1, A_2, \ldots, A_N, separated by spaces.
  • The third line contains the required skill levels of each task, B_1, B_2, \ldots, B_M, separated by spaces.

Output

Print the maximum sales amount Takahashi can obtain in a single line. Note that the answer is a non-negative integer not exceeding 2 \times 10^{14}.

Sample Input 1

3 3 500
5 3 1
2 4 6

Sample Output 1

1000

Sample Input 2

5 4 1000
10 3 7 1 8
5 2 9 4

Sample Output 2

4000

Sample Input 3

7 8 1000000000
100 50 80 30 60 90 10
20 40 60 80 100 55 35 75

Sample Output 3

6000000000