Remove items so any k prices stay under a threshold

A store is planning a holiday promotion from a list of candidate items with known prices. Shoppers may pick any k items from whatever stays on the list, and the store wants every such group of k items to cost at most threshold in total.

Implement:

def reduce_gifts(prices: list[int], k: int, threshold: int) -> int

Return the minimum number of items to remove from prices so that the sum of any k remaining items is at most threshold. If fewer than k items remain, no group of k exists and the condition is satisfied.

Constraints

• 1 <= k <= n <= 10^5, where n = len(prices)
• 1 <= prices[i] <= 10^9
• 1 <= threshold <= 10^9

Example 1

prices = [8, 1, 5, 7, 2], k = 2, threshold = 9  ->  2

The most expensive pair is 8 + 7 = 15. Remove 8: the most expensive pair is now 7 + 5 = 12. Remove 7: the most expensive pair is 5 + 2 = 7, which fits. Two removals.

Example 2

prices = [10, 10, 10, 10], k = 1, threshold = 9  ->  4

Every single item is over the limit, so all four must go.