Overview

This is a problem where you select \(M\) part-time workers and assign them to tasks such that each task’s requirement \(D_j\) is met, maximizing the total satisfaction \(\sum(A_i-D_j)\). The conclusion is that it can be solved by “selecting the top \(M\) workers by skill level, then checking assignability using sorting.”

Analysis

1. Transforming the objective function

For any assignment, the total satisfaction is [ \sum_{\text{assignment}}(A_i - Dj)=\left(\sum{\text{selected workers}}Ai\right)-\left(\sum{\text{all tasks}}D_j\right) ]

Since \(\sum D_j\) is fixed on the task side, what we want to maximize is only “the sum of \(A\) of the \(M\) chosen workers.” In other words, “as long as an assignment is feasible, choosing workers with higher skills is always better.”

2. Is choosing the “top \(M\) workers” always optimal?

From an optimization perspective, the top \(M\) workers maximize \(\sum A\). However, the question is whether an assignment is feasible (i.e., \(A_i \ge D_j\) holds for all tasks).

Here is an important observation:

• Whether a given set of \(M\) workers can be feasibly assigned can be determined by sorting their skills in ascending order and the requirements \(D\) in ascending order, then checking if \(a_k \ge d_k\) holds for all \(k\). (Greedily assigning the smallest available skill to the smallest requirement is the safest strategy.)

Furthermore, the decisive point is:

• The sorted ascending sequence of the top \(M\) workers’ skills can be shown to have each element greater than or equal to the corresponding element in the sorted ascending sequence of any other set of \(M\) workers. Intuitively, the top \(M\) workers form “the strongest set of size \(M\),” so even looking from the bottom, they are never weaker.

Therefore, - If even the top \(M\) workers fail the sorted comparison (i.e., \(a_k < d_k\) for some \(k\)), then no matter which \(M\) workers are chosen, it is always impossible (the answer is \(-1\)). - If the top \(M\) workers pass, then since \(\sum A\) is maximized, the total satisfaction at that point is the maximum.

3. Why naive approaches don’t work

• If you try to “enumerate all assignments (matchings)” or directly apply “bipartite matching,” it is far too slow for \(N,M \le 2\times 10^5\).
• Since the objective function separates nicely in this problem, we can fix the chosen workers as the top \(M\) and check assignment feasibility in \(O(N\log N)\).

Algorithm

1. Sort the skill array \(A\) of part-time workers in descending order.
2. Select the top \(M\) workers chosen = A[:M] and compute chosen_sum = sum(chosen). (This is the maximum possible \(\sum A\).)
3. Sort chosen in ascending order, and also sort the requirement array \(D\) in ascending order.
4. Pair them using zip(chosen, D) in ascending order; if there exists even one pair where \(a < d\), the assignment is infeasible, so output -1.
5. If \(a \ge d\) holds for all pairs, the assignment is feasible, and the maximum satisfaction is [ chosen_sum - \sum D ] which we output.

(Example) \(A = [8,5,4],\ M=2,\ D=[6,4]\) The top 2 workers are \([8,5]\), sorted ascending: \([5,8]\), \(D\) sorted ascending: \([4,6]\). \(5\ge4,\ 8\ge6\), so it is feasible. The answer is \((8+5)-(6+4)=3\).

Complexity

• Time complexity: \(O(N\log N + M\log M)\) (mainly sorting)
• Space complexity: \(O(N+M)\) (for storing arrays)

Implementation Notes

• The sum of the top \(M\) workers can be obtained by simply sorting in descending order and taking the first \(M\) elements.

• Feasibility checking is concise and safe by sorting both in ascending order and comparing from the front.

• Since the input can be large, sys.stdin.buffer.read() is used for fast input.

  Source Code

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()

---

This editorial was generated by gpt-5.2-high.