Overview

For each product, choose whether to “buy at the regular price” or “apply a coupon to get the sale price,” and minimize the total cost while using coupons on at most \(K\) items.

Analysis

When a coupon is used, the payment for product \(i\) decreases from \(A_i\) to \(B_i\). In other words, the “amount saved” is
\(A_i - B_i\) yen.

The key observation is as follows:

• First, if we buy all products at their regular prices, the total is \(\sum A_i\).
• From there, for each product where a coupon is used, the total decreases by \((A_i - B_i)\) yen.
• Therefore, “minimizing the total” is equivalent to “maximizing the total savings \((A_i - B_i)\).”

Thus, the optimal strategy is to select at most \(K\) products with the largest savings, in descending order of their discount amount.

If we naively enumerate all possible choices of which products to apply coupons to, there are up to \(\binom{N}{K}\) combinations, which is far too many to handle when \(N \le 2\times 10^5\) (TLE).
Since each product’s effect (discount amount) is independent with no interactions between products, we can reduce this to a greedy approach of selecting the largest discounts first.

Example: - \((A,B)=(10,7),(8,3),(5,5)\), \(K=2\) - Savings are \(3,5,0\) - Selecting the top two in descending order: \(5,3\) → Total is \((10+8+5) - (5+3)=23-8=15\)

Algorithm

1. Compute the total total as \(\sum A_i\).
2. For each product, store the savings s = A_i - B_i in an array savings.
3. Sort savings in descending order.
4. Subtract the sum of the top \(K\) savings \(\sum_{j=1}^{K} savings[j]\) from total.
5. Output total.
   (When \(K=0\), nothing is subtracted, and the answer is simply \(\sum A_i\).)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting the savings)
• Space complexity: \(O(N)\) (for the savings array)

Implementation Notes

• Since \(A_i, B_i\) can be up to \(10^9\) and \(N\) up to \(2\times 10^5\), the total can reach approximately \(2\times 10^{14}\). In Python, integers grow automatically so this is safe, but in other languages, 64-bit integers are required.

• Use savings.sort(reverse=True) for descending order, and sum(savings[:K]) to sum only the top \(K\) values.

• Since the input can be large, using sys.stdin.readline ensures stable performance.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    total = 0
    savings = []
    for _ in range(N):
        A, B = map(int, input().split())
        total += A
        savings.append(A - B)

    savings.sort(reverse=True)
    total -= sum(savings[:K])
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.