Overview

Given \(N\) members, the problem asks you to select members satisfying the conditions “exactly \(M\) experienced members” and “exactly \(K\) members in total,” and maximize the total skill value.

Analysis

The key point of this problem is that the number of people to select from experienced members and from beginners is fixed.

• Total number of people to select: \(K\)
• Number of experienced members to select: \(M\)
• Number of beginners to select: \(K - M\)

To achieve the goal of “maximizing the total skill,” we can see that we should select the top \(M\) experienced members by skill and the top \(K - M\) beginners by skill. Since the selection of experienced members and beginners do not affect each other (they are independent), we can apply the simple “greedy” approach of selecting the top members from each group.

Additionally, if any of the following conditions are met, the required number of members cannot be secured, so the answer is \(-1\): - The total number of experienced members is less than \(M\). - The total number of beginners is less than \(K - M\).

Algorithm

1. Group separation: Divide all members into two lists: experienced (\(H_i=1\)) and beginners (\(H_i=0\)).
2. Condition check: Verify that the number of elements in the experienced list is at least \(M\) and the number of elements in the beginner list is at least \(K - M\). If not satisfied, output \(-1\) and terminate.
3. Sort: Sort each list in descending order of skill.
4. Sum calculation: Compute the sum of the first \(M\) elements of the experienced list and the sum of the first \(K - M\) elements of the beginner list, and output their total.

Complexity

• Time complexity: \(O(N \log N)\)
  • Separating members takes \(O(N)\), and sorting the lists takes \(O(N \log N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the lists storing member skills.

Implementation Tips

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), which is relatively large, in Python you can reduce execution time by reading all input at once using sys.stdin.read().split() or similar methods.

• Using slices: In Python, you can concisely compute the sum of the top several elements using slices like sum(list[:count]).

• Corner cases: The cases \(M=0\) and \(M=K\) are also handled correctly by this algorithm.

  Source Code

import sys

def main():
    # 入力を標準入力からすべて読み込み、空白で分割してトークンのリストを作成します
    # これは大量の入力を高速に処理するための一般的な手法です
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not data:
        return
    
    # N: メンバーの総数, K: 選ぶメンバーの人数, M: 必要な経験者の人数
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    
    # 経験者のスキルと初心者のスキルをそれぞれ別のリストに格納します
    experienced_skills = []
    beginner_skills = []
    
    # data[3]以降に各メンバーのH_iとP_iが交互に並んでいます
    # 各メンバーの情報をループで処理します
    ptr = 3
    for _ in range(N):
        # h: 経験の有無 (1なら経験者, 0なら初心者), p: スキル
        h = data[ptr]
        p = int(data[ptr+1])
        if h == '1':
            experienced_skills.append(p)
        else:
            beginner_skills.append(p)
        ptr += 2
        
    # 選ぶK人のうち経験者がちょうどM人必要なので、初心者はちょうどK-M人必要です
    num_beginners_needed = K - M
    
    # 必要な人数分それぞれのメンバーが存在するか確認します
    # 存在しない場合は条件を満たす選び方ができないため -1 を出力します
    if len(experienced_skills) < M or len(beginner_skills) < num_beginners_needed:
        print("-1")
        return
        
    # 総合力（スキルの合計）を最大化するため、それぞれのリストを降順（大きい順）にソートします
    experienced_skills.sort(reverse=True)
    beginner_skills.sort(reverse=True)
    
    # 経験者の上位M人のスキル合計と、初心者の上位K-M人のスキル合計を計算します
    # Pythonのスライスとsum関数を用いて効率的に合計を求めます
    max_total_skill = sum(experienced_skills[:M]) + sum(beginner_skills[:num_beginners_needed])
    
    # 結果を出力します
    print(max_total_skill)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3-flash-preview.