Overview

Given \(N\) items, use a coupon that can make up to \(K\) of the most expensive items free, and minimize the total amount paid.

Analysis

In this problem, we want to minimize the total amount paid, so it is most effective to use the coupon to make the most expensive items free.

For example, if the item prices are \([100, 200, 300]\) yen and the coupon can be used \(1\) time, making the most expensive \(300\) yen item free results in a payment of \(100 + 200 = 300\) yen.

Therefore, the optimal strategy is to sort the price list in descending order and make the top \(K\) items free. The sum of the prices of the remaining items (those after the \(K\)-th position) is the answer.

If we naively try to “exhaustively search which items to select,” the number of combinations becomes extremely large and cannot be solved within the time limit (TLE). However, since the optimal solution can be obtained simply by “making the \(K\) most expensive items free,” we can solve this efficiently using sorting.

Algorithm

1. Read the list of item prices \(D\).
2. Sort the price list in descending order (most expensive items come first).
3. In the sorted list, compute the sum of elements from index \(K\) onward (i.e., the items that are not made free).
4. Output that sum.

For example, when \(D = [100, 200, 300], K = 1\): - After sorting: \([300, 200, 100]\) - Sum from index \(1\) onward: \(200 + 100 = 300\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (for storing the input list)

Implementation Notes

• Use sort(reverse=True) to sort in descending order.

• The sum can be easily computed with sum(D[K:]).

• Even when \(K > N\), no out-of-range slice error occurs (the sum of an empty list is 0).

  Source Code

N, K = map(int, input().split())
D = list(map(int, input().split()))

D.sort(reverse=True)

ans = sum(D[K:])
print(ans)

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