Overview

This problem asks you to select \(K\) people including exactly \(M\) experienced members, maximizing the total skill \(P\) of the selected people. The optimal strategy is to separate experienced and novice members and “take the required number of people with the highest skills” from each group.

Analysis

Key Insight

The only constraint is a headcount constraint: “exactly \(M\) out of the \(K\) selected people must be experienced.” There are no compatibility requirements or additional conditions among experienced members or among novice members.

Given this, the optimal solution is intuitively as follows:

• For the \(M\) experienced slots, it is best to select the \(M\) people with the highest skills among all experienced members.
• For the \(K-M\) novice slots, it is best to select the \(K-M\) people with the highest skills among all novice members.

This is because if you select a lower-skilled person in the experienced slots, you can swap them for another experienced person with higher skill — the “number of experienced members remains the same” while the total skill increases, so there is no reason to select the lower-skilled person (the swap always improves the solution).

Why a Brute-Force Approach Fails

The number of ways to choose \(K\) people from \(N\) is \(\binom{N}{K}\), and for \(N \le 2\times10^5\), exhaustive search is completely infeasible (TLE).

Since this problem only has a headcount constraint, we can maximize the total by simply “taking from the top” without exhaustive search.

Concrete Example

If the experienced members’ skills are [10, 7, 3], the novice members’ skills are [8, 6, 1], and \(K=4, M=2\): - Top 2 from experienced: \(10 + 7\) - Top 2 from novice: \(8 + 6\)

The maximum total is \(31\).

Algorithm

1. Read the input and, based on \(H_i\), separate the skills \(P_i\) into:
   • Experienced list exp
   • Novice list nov
2. Check whether a valid selection is possible:
   • If there are fewer than \(M\) experienced members, or fewer than \(K-M\) novice members, it is impossible, so output -1.
3. Sort exp and nov each in descending order.
4. Sum the first \(M\) elements of exp and the first \(K-M\) elements of nov, and output the result.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the experienced and novice lists)
• Space complexity: \(O(N)\) (storing skills in lists)

Implementation Notes

• Always check first whether a valid selection exists (len(exp) < M or len(nov) < K-M).

• Since we want to maximize, sort in descending order (sort(reverse=True)) and take the required number of elements from the front.

• In Python, you can concisely compute the sum using slicing, such as sum(exp[:M]).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K, M = map(int, input().split())
    exp = []
    nov = []
    for _ in range(N):
        h, p = map(int, input().split())
        if h == 1:
            exp.append(p)
        else:
            nov.append(p)

    if len(exp) < M or len(nov) < K - M:
        print(-1)
        return

    exp.sort(reverse=True)
    nov.sort(reverse=True)
    ans = sum(exp[:M]) + sum(nov[:K - M])
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.