Overview

Given \(N\) types of sweets, select \(K\) of them to maximize the total “satisfaction” (base tastiness \(T_i\) + preference bonus \(C_i\)).

Analysis

The most important point in this problem is that each sweet’s evaluation is determined by a single value: the sum of \(T_i\) and \(C_i\).

Takahashi wants to maximize the total satisfaction. The satisfaction obtained by choosing sweet \(i\) can be calculated as \(S_i = T_i + C_i\). When selecting some items from a collection to maximize their total, the greedy strategy of “choosing items in decreasing order of their individual values” is optimal.

For example, consider the following sweets (\(K=2\)): - Sweet 1: \(T_1=10, C_1=5 \Rightarrow S_1=15\) - Sweet 2: \(T_2=20, C_2=-10 \Rightarrow S_2=10\) - Sweet 3: \(T_3=5, C_3=15 \Rightarrow S_3=20\)

In this case, the satisfactions \(S_i\) are \(15, 10, 20\) respectively. To maximize the total, the best choice is to select “Sweet 3 (20)” and “Sweet 1 (15)”.

Therefore, the problem can be solved with the following steps: 1. For all sweets, compute the satisfaction \(S_i = T_i + C_i\). 2. Sort the computed satisfactions in descending order. 3. Sum the top \(K\) satisfactions.

Algorithm

1. Read input: Read \(N, K\) and each sweet’s \(T_i, C_i\).
2. Compute satisfactions: For each \(i\), compute \(S_i = T_i + C_i\) and store it in a list.
3. Sort: Sort the list in descending order.
4. Compute the total: Sum the first \(K\) elements of the sorted list and output the result.

Complexity

• Time complexity: \(O(N \log N)\)
  • Computing satisfactions takes \(O(N)\), sorting takes \(O(N \log N)\), and summing the top \(K\) elements takes \(O(K)\). Overall, the sorting step dominates. Since \(N = 2 \times 10^5\), this complexity is well within the time limit.
• Space complexity: \(O(N)\)
  • A list is needed to store the satisfactions of \(N\) sweets.

Implementation Notes

• Fast input: Since \(N\) can be as large as \(2 \times 10^5\), in Python using sys.stdin.read().split() to read all input at once makes processing faster.

• Sort order: By specifying sort(reverse=True), you can easily sort in descending order.

• Slicing and summing: Using a slice like sum(satisfactions[:K]) provides a concise way to compute the sum of the top \(K\) elements.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白（スペースや改行）で分割してリストにします
    # 競技プログラミングにおいて、大量の入力を高速に処理する一般的な手法です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します
    if not input_data:
        return
    
    # 文字列のリストを整数のリストに一括変換します
    # map関数をlistで包むことで、高速に変換処理が行われます
    data = list(map(int, input_data))
    
    # 1つ目の要素が種類数 N、2つ目の要素が選ぶ個数 K です
    N = data[0]
    K = data[1]
    
    # 各お菓子の満足度（T_i + C_i）を計算します
    # T_i と C_i のペアはインデックス2から始まります
    # i番目のお菓子の T_i は data[2 + 2*i]、C_i は data[3 + 2*i] に位置します
    satisfactions = [data[i] + data[i+1] for i in range(2, 2 * N + 2, 2)]
    
    # 満足度が高い順にお菓子を選ぶため、降順（大きい順）にソートします
    satisfactions.sort(reverse=True)
    
    # 上位 K 個の満足度の合計を計算して出力します
    # Pythonのスライス（[:K]）とsum関数を組み合わせることで効率的に合計を求められます
    print(sum(satisfactions[:K]))

if __name__ == '__main__':
    solve()

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