Overview

Given \(N\) business days each with a required skill level \(H_i\) and sales \(S_i\), we need to determine whether all part-time workers (each with skill \(P_j\)) can be assigned to workable days (\(H_i \le P_j\)) without overlap, and if possible, maximize the total sales.

Analysis

Each part-time worker can only work on days where the required skill does not exceed their own skill, i.e., worker \(j\) can only choose days satisfying \(H_i \le P_j\). Also, at most one worker can be assigned to each day.

Key Observations

• We need to consider both “whether a valid assignment exists” and “maximum profit” simultaneously.
• Workers with lower skills have fewer available days, so it is natural to process workers in ascending order of skill.
• When processing a worker with skill \(p\), it is optimal to choose the day with the maximum sales \(S_i\) among currently assignable days (\(H_i \le p\)).

Why a Naive Approach is Difficult

• Exploring all possible assignments leads to combinatorial explosion (on the scale of choosing and arranging \(M\) from \(N\)).
• Directly constructing a bipartite matching has edges defined by “\(H_i \le P_j\)”, which can be extremely numerous (worst case \(NM\)), making it impractical for constraints up to \(2 \times 10^5\).

How to Solve It

We efficiently implement the greedy strategy of “processing in order of skill and selecting the maximum sales day among currently available days.” - We use a priority queue (heap) to manage the set of “currently available days.”

Algorithm

1. Prepare business days as pairs \((H_i, S_i)\) and sort them in ascending order of required skill \(H_i\).
2. Sort the workers’ skills \(P_j\) in ascending order as well.
3. Process workers in order from the lowest skill:
   • Let the current worker’s skill be \(p\).
   • Add all not-yet-seen business days satisfying \(H_i \le p\) to the heap (inserting their sales \(S_i\)).
   • If the heap is empty, there are no available days for this worker, so the assignment is impossible (output -1).
   • Extract the maximum \(S_i\) from the heap, assign that day to this worker, and add it to the total.
4. If all workers are successfully processed, output the total sales.

Why This Greedy Approach is Correct (Intuition)

Workers with lower skills have fewer options, so deferring them makes it more likely to get stuck. On the other hand, days available at skill level \(p\) (i.e., \(H_i \le p\)) will always remain available for future workers with higher skills. Therefore, “taking the highest-sales day among currently available ones” does not unnecessarily narrow future options and maximizes total sales.

(Simple example) - Days: \((H,S)=(1,10),(2,100)\) - Workers: \(P=(1,2)\) When \(P=1\), the only available day is \(H=1\), so take it (10). Next, \(P=2\) can take the remaining day \(H=2\) (100). The total of 110 is the maximum.

Complexity

• Time complexity: Sorting takes \(O(N\log N + M\log M)\), and each day is pushed once and each worker pops once, so heap operations are \(O((N+M)\log N)\). Overall: \(O((N+M)\log N)\).
• Space complexity: At most \(O(N)\) for the business day array and the heap.

Implementation Notes

• Python’s heapq is a min-heap, so to extract the maximum value, insert \(-S_i\) and negate the sign when extracting.

• Sort the business days in ascending order of \(H_i\) and advance a pointer idx, adding days where “\(H_i \le p\)” to the heap. This way, the entire array is traversed only once.

• If the heap becomes empty for any worker, immediately output -1 and terminate. This handles both the feasibility check and maximization simultaneously.

  Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)

    days = []
    for _ in range(N):
        h = next(it)
        s = next(it)
        days.append((h, s))
    days.sort()

    P = [next(it) for _ in range(M)]
    P.sort()

    heap = []
    idx = 0
    total = 0

    for p in P:
        while idx < N and days[idx][0] <= p:
            heapq.heappush(heap, -days[idx][1])
            idx += 1
        if not heap:
            print(-1)
            return
        total += -heapq.heappop(heap)

    print(total)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.