Overview

A problem where you select a specified number of “experienced” and “beginner” members to maximize the total skill.

Analysis

In this problem, we select \(K\) people from \(N\) members, with the constraint that exactly \(M\) of them must be experienced (\(H_i = 1\)).

What about a naive approach?

A straightforward method would be to try all combinations, but since the number of members can be up to \(2 \times 10^5\), this would obviously result in TLE (Time Limit Exceeded).

Key observation

To maximize the total skill: - We should select the top \(M\) people with the highest skills from the experienced members. - We should also select the top \((K - M)\) people with the highest skills from the beginners.

In other words, we create an “experienced list” and a “beginner list,” and sort each in descending order of skill.

Further optimization

After sorting the lists, by precomputing prefix sums from the beginning, we can quickly calculate the total skill for any number of selected people.

Finally, we check whether it is possible to select exactly \(M\) experienced members, and if not, output -1.

Algorithm

1. Read the input and separate members into “experienced” and “beginners.”
2. Sort both lists in descending order of skill.
3. Precompute prefix sums from the beginning for each list.
4. Check whether there are at least \(M\) experienced members and at least \((K - M)\) beginners.
   • If not, output -1.
5. Fix the selection of exactly \(M\) experienced members, and select the remaining from beginners.
6. Compute the maximum total skill for this case.

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing lists and prefix sums)

Implementation Notes

• As with a cumsum function, inserting 0 at the beginning of the prefix sum array makes boundary handling easier.
• In the final loop, only consider the case where exactly \(M\) experienced members are selected.

## Source Code

```python
import sys
from heapq import nlargest

input = sys.stdin.read
data = input().split()

N = int(data[0])
K = int(data[1])
M = int(data[2])

members = []
idx = 3
for i in range(N):
    H = int(data[idx])
    P = int(data[idx+1])
    members.append((H, P))
    idx += 2

# 経験者と初心者に分ける
experts = [p for h, p in members if h == 1]
beginners = [p for h, p in members if h == 0]

# スキルの高い順にソート
experts.sort(reverse=True)
beginners.sort(reverse=True)

# 累積和を計算
def cumsum(arr):
    cum = [0]
    for x in arr:
        cum.append(cum[-1] + x)
    return cum

cum_experts = cumsum(experts)
cum_beginners = cumsum(beginners)

# 条件を満たすかチェック
num_experts = len(experts)
num_beginners = len(beginners)

if num_experts < M or num_beginners < (K - M):
    print(-1)
else:
    max_power = -1
    # 経験者をM人選ぶ
    for i in range(min(M, num_experts) + 1):
        if i > M or (M - i) > num_beginners:
            continue
        expert_sum = cum_experts[i] if i <= num_experts else 0
        beginner_sum = cum_beginners[K - i] if (K - i) <= num_beginners else 0
        total = expert_sum + beginner_sum
        if i == M:
            max_power = max(max_power, total)
    
    print(max_power)

---

This editorial was generated by qwen3-coder-480b.