/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、アルバイト N 人を抱える店舗の店長です。今度の休日に M 個の業務をこなす必要があり、各業務にちょうど 1 人のアルバイトを割り当てなければなりません。
アルバイトにはそれぞれ 1 から N までの番号が付けられており、アルバイト i のスキル値は A_i です。また、業務にはそれぞれ 1 から M までの番号が付けられており、業務 j の要求スキル値は D_j です。
アルバイト i が業務 j を担当した場合、その満足度は A_i - D_j で計算されます。満足度が負になるとそのアルバイトは不満を感じてしまうため、高橋君はすべての担当者の満足度が 0 以上（すなわち不満を感じない状態）となるように割り当てたいと考えています。
具体的には、N 人のアルバイトの中から M 人を選び、選んだ M 人と M 個の業務を一対一に対応させて割り当てます。すなわち、業務 j の担当者を f(j) と表したとき、以下の条件をすべて満たす割り当て f を考えます。
- すべての業務 j (1 \leq j \leq M) にちょうど 1 人のアルバイトが担当者として割り当てられている。
- 異なる業務には異なるアルバイトが割り当てられている。すなわち、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
- 1 行目には、アルバイトの人数を表す整数 N と、業務の個数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、各アルバイトのスキル値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 3 行目には、各業務の要求スキル値を表す整数 D_1, D_2, \ldots, D_M が、スペース区切りで与えられる。
出力
条件を満たす割り当てが存在する場合は、満足度の合計の最大値を整数で 1 行に出力せよ。存在しない場合は -1 を 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
Score : 400 pts
Problem Statement
Takahashi is the manager of a store with N part-time workers. He needs to complete M tasks on an upcoming holiday, and must assign exactly 1 part-time worker to each task.
The part-time workers are numbered from 1 to N, and the skill level of worker i is A_i. The tasks are numbered from 1 to M, and the required skill level of task j is D_j.
When worker i is assigned to task j, their satisfaction is calculated as A_i - D_j. Since a worker becomes dissatisfied if their satisfaction is negative, Takahashi wants to make an assignment such that every assigned worker's satisfaction is 0 or more (i.e., no one is dissatisfied).
Specifically, he selects M workers out of the N part-time workers and assigns the selected M workers to the M tasks in a one-to-one correspondence. That is, letting f(j) denote the worker assigned to task j, he considers an assignment f that satisfies all of the following conditions:
- Exactly 1 part-time worker is assigned to each task j (1 \leq j \leq M).
- Different tasks are assigned different workers. That is, if j \neq j', then f(j) \neq f(j'). (Some workers may not be assigned to any task.)
- For every worker assigned to a task, their satisfaction is 0 or more. That is, for every task j (1 \leq j \leq M), A_{f(j)} \geq D_j holds.
If an assignment satisfying these conditions exists, find the maximum value of the total satisfaction of the M assigned workers, \displaystyle\sum_{j=1}^{M}(A_{f(j)} - D_j). If no valid assignment exists, output -1.
Constraints
- 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)
- All input values are integers.
Input
N M A_1 A_2 \ldots A_N D_1 D_2 \ldots D_M
- The first line contains an integer N representing the number of part-time workers and an integer M representing the number of tasks, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the skill levels of each worker, separated by spaces.
- The third line contains integers D_1, D_2, \ldots, D_M representing the required skill levels of each task, separated by spaces.
Output
If a valid assignment exists, output the maximum value of the total satisfaction as an integer on a single line. If no valid assignment exists, output -1 on a single line.
Sample Input 1
4 3 5 3 7 1 2 4 6
Sample Output 1
3
Sample Input 2
3 3 1 2 3 4 5 6
Sample Output 2
-1
Sample Input 3
7 5 10 25 8 30 15 5 20 3 12 7 18 25
Sample Output 3
35