概要

各業務の要求 \(D_j\) を満たすようにアルバイトを \(M\) 人選んで割り当て、満足度合計 \(\sum(A_i-D_j)\) を最大化する問題です。結論として「スキルが高い順に上位 \(M\) 人を選び、割り当て可能かをソートして判定」すれば解けます。

考察

1. 目的関数の形を変形する

どの割り当てでも、満足度合計は [ \sum_{割当}(A_i - Dj)=\left(\sum{選ばれたアルバイトの}Ai\right)-\left(\sum{全業務の}D_j\right) ] です。

ここで \(\sum D_j\) は業務側で固定なので、最大化したいのは「選ぶ \(M\) 人の \(A\) の合計」だけになります。
つまり「割り当てさえ可能なら、スキルが高い人を選ぶほど得」です。

2. では「上位 \(M\) 人」を選べば必ず最適？

最適化の観点では上位 \(M\) 人が最も \(\sum A\) を大きくします。しかし、問題は 割り当て可能（全ての業務で \(A_i \ge D_j\) を満たす）かどうかです。

ここで重要な観察があります：

• ある \(M\) 人の集合で割り当て可能かどうかは、
  「その \(M\) 人のスキルを小さい順に並べた列」と「要求 \(D\) を小さい順に並べた列」を比べ、全てで \(a_k \ge d_k\) が成り立つかで判定できます。
  （小さい要求から順に、今使える中で一番小さいスキルを当てるのが最も安全な貪欲です）

さらに決定的なのは：

• スキル上位 \(M\) 人を小さい順に並べた列は、どんな他の \(M\) 人集合を小さい順に並べた列よりも「各要素が大きい（または等しい）」ことが示せます。
  直感的には、上位 \(M\) 人は「サイズ \(M\) の集合として最強」なので、下から見ても弱くなりません。

よって、 - 上位 \(M\) 人ですら、ソート比較でどこか \(a_k < d_k\) になるなら、どんな \(M\) 人を選んでも必ず不可能（答えは \(-1\)）。 - 上位 \(M\) 人で可能なら、\(\sum A\) が最大なので そのときの満足度合計が最大。

3. 素朴な方法がダメな理由

• 「全割り当て（マッチング）を探索」や「二部マッチング」をそのまま行うと、\(N,M \le 2\times 10^5\) では到底間に合いません。
• この問題は目的関数がうまく分離できるため、選ぶ人は上位 \(M\) 人に決め打ちし、割り当て可能性だけを \(O(N\log N)\) で判定できます。

アルゴリズム

1. アルバイトのスキル配列 \(A\) を降順ソートする。
2. 上位 \(M\) 人 chosen = A[:M] を選び、chosen_sum = sum(chosen) を計算する。
   （これが取りうる最大の \(\sum A\)）
3. chosen を昇順、要求配列 \(D\) も昇順にソートする。
4. zip(chosen, D) で小さい順に対応させ、1つでも \(a < d\) があれば割り当て不可能なので -1。
5. 全て \(a \ge d\) なら割り当て可能で、最大満足度は [ chosen_sum - \sum D ] を出力する。

（例）
\(A = [8,5,4],\ M=2,\ D=[6,4]\)
上位2人は \([8,5]\)、昇順で \([5,8]\)、\(D\) 昇順で \([4,6]\)。
\(5\ge4,\ 8\ge6\) なので可能。答えは \((8+5)-(6+4)=3\)。

計算量

• 時間計算量: \(O(N\log N + M\log M)\)（主にソート）
• 空間計算量: \(O(N+M)\)（配列保持）

実装のポイント

• 上位 \(M\) 人の合計は、降順ソートして先頭 \(M\) 個を取るだけでよいです。

• 割り当て可能性判定は、両方を昇順にして前から比較するのが簡潔で安全です。

• 入力が大きいので、sys.stdin.buffer.read() による高速入力にしてあります。

  ソースコード

import sys

def main():
    it = map(int, sys.stdin.buffer.read().split())
    N = next(it)
    M = next(it)
    A = [next(it) for _ in range(N)]
    D = [next(it) for _ in range(M)]

    A.sort(reverse=True)
    chosen = A[:M]
    chosen_sum = sum(chosen)

    chosen.sort()
    D.sort()

    for a, d in zip(chosen, D):
        if a < d:
            print(-1)
            return

    print(chosen_sum - sum(D))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。