Overview

Define the satisfaction of each snack as the sum of its base points \(T_i\) and correction value \(C_i\), then select the top \(K\) snacks with the highest satisfaction and find their total.

Analysis

The final satisfaction of each snack can be simply computed as \(T_i + C_i\).
Therefore, by calculating this value for all snacks and sorting in descending order, the optimal solution is obtained by simply selecting the top \(K\) items.

A naive approach of searching for the snack with the maximum satisfaction each time (e.g., linear search each time) would result in a time complexity of \(O(N^2)\), which would cause TLE since \(N\) can be up to \(2 \times 10^5\).
However, by sorting everything at once, we can efficiently extract the top \(K\) items.

Algorithm

1. For each snack, compute \(T_i + C_i\) and store it in a list.
2. Sort the list in descending order.
3. Compute and output the sum of the top \(K\) elements.

Example

Sample input:

4 2
3 2
1 4
5 -1
2 3

Computed satisfaction values: - Snack 1: \(3 + 2 = 5\) - Snack 2: \(1 + 4 = 5\) - Snack 3: \(5 + (-1) = 4\) - Snack 4: \(2 + 3 = 5\)

Sorted list (descending): \([5, 5, 5, 4]\)

Selecting the top 2, the total is \(5 + 5 = 10\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (list to store satisfaction values)

Implementation Notes

• It is efficient to compute the satisfaction each time input is received and append it to the list.

• Using sort(reverse=True) makes descending sort straightforward.

• Use the slice [:K] to extract the top \(K\) items and sum() to compute the total.

  Source Code

N, K = map(int, input().split())
satisfactions = []

for _ in range(N):
    T, C = map(int, input().split())
    satisfactions.append(T + C)

satisfactions.sort(reverse=True)
print(sum(satisfactions[:K]))

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