Overview

This is a problem where you calculate the “final satisfaction” \(T_i + C_i\) for each snack, then find the total sum when selecting the top \(K\) snacks in descending order of that value.

Analysis

The key insight in this problem is that the “selection criterion” is simply the magnitude of the final satisfaction \(T_i + C_i\) itself, with no interactions or dependencies between different snacks. In other words, each snack can be evaluated independently, and it is optimal to take the \(K\) snacks with the highest final satisfaction.

For example, if \(N=5, K=2\) and the final satisfactions are \([8, 3, 10, 7, 7]\), we select the top 2 values: \(10\) and \(8\), giving an answer of \(18\). Even if there are ties (e.g., two values of \(7\)), choosing any of them yields the same total (since you can select the same values as the top \(K\) set), so there is no issue.

If we naively consider “choosing \(K\) items from all combinations,” the number of combinations is \(\binom{N}{K}\), which is computationally infeasible (guaranteed TLE). However, since each item is evaluated independently in this problem, it can be solved by simply sorting and summing the first \(K\) elements.

Algorithm

1. For each snack, calculate the final satisfaction \(v_i = T_i + C_i\) and store it in an array.
2. Sort the array in descending order (largest first).
3. Output the sum of the first \(K\) elements (\(v_1, v_2, \dots, v_K\)).

Complexity

• Time complexity: Dominated by sorting, so \(O(N \log N)\)
• Space complexity: \(O(N)\) for storing the satisfaction array

Implementation Notes

• \(T_i, C_i\) can be up to \(\pm 10^9\), and \(T_i + C_i\) or their sum can be even larger, so (while this is not an issue in Python) in other languages it is safe to use \(64\)-bit integers (long long, etc.).

• Since the input can have up to \(2 \times 10^5\) lines, using sys.stdin.readline in Python allows for faster reading.

• You can sort in descending order with vals.sort(reverse=True) and concisely compute the sum of the top \(K\) elements with sum(vals[:K]).

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    vals = []
    for _ in range(N):
        T, C = map(int, input().split())
        vals.append(T + C)
    vals.sort(reverse=True)
    print(sum(vals[:K]))

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.