Overview

Given \(N\) products where you can use coupons on at most \(K\) of them to purchase at sale prices, this problem asks to minimize the total purchase amount. It can be solved using a greedy approach that prioritizes using coupons on products with the largest discounts.

Analysis

Key Insight

First, consider “how much you save” by using a coupon on each product.

If you use a coupon on product \(i\): - Regular price \(A_i\) yen → Sale price \(B_i\) yen

In other words, you save discount amount = \(A_i - B_i\) yen.

Problem Reformulation

If you buy all products at regular prices, the total is \(\sum_{i=1}^{N} A_i\) yen.

From this, the price decreases by the discount amount for each product where a coupon is used.

Therefore, minimizing the purchase amount = maximizing the total discount is an equivalent reformulation.

Correctness of the Greedy Approach

By using coupons on products with the largest discounts first, the total discount is maximized.

Concrete Example: When \(N = 3\), \(K = 2\)

Product	Regular Price \(A_i\)	Sale Price \(B_i\)	Discount \(A_i - B_i\)
1	100	80	20
2	200	120	80
3	150	140	10

• Total regular price: \(100 + 200 + 150 = 450\) yen
• Sorted by discount (descending): Product 2 (80 yen), Product 1 (20 yen), Product 3 (10 yen)
• Total discount of top \(K=2\) items: \(80 + 20 = 100\) yen
• Minimum purchase amount: \(450 - 100 = 350\) yen

Algorithm

1. Calculate total_normal by summing all regular prices \(A_i\)
2. Store the discount amount \(A_i - B_i\) for each product in a list
3. Sort the discounts in descending order
4. Calculate total_discount by summing the top \(K\) discounts
5. The answer is total_normal - total_discount

Minimum purchase amount = Total regular price of all products - Sum of top K discounts

Complexity

• Time Complexity: \(O(N \log N)\)
  • Reading input: \(O(N)\)
  • Sorting: \(O(N \log N)\)
  • Summing top \(K\) items: \(O(K) \leq O(N)\)
• Space Complexity: \(O(N)\)
  • List to store discounts

Implementation Notes

1. Calculating Discounts: Due to the constraint \(B_i \leq A_i\), the discount \(A_i - B_i\) is always \(0\) or greater. Using a coupon on a product with \(0\) discount causes no loss.

2. Descending Sort: Use sort(reverse=True) to arrange discounts in descending order.

3. Getting Top K with Slicing: discounts[:K] extracts the first \(K\) elements. Even if \(K\) is larger than the list length, Python handles this correctly without errors.

4. Watch for Overflow: Since \(A_i\) can be up to \(10^9\) and \(N\) can be up to \(2 \times 10^5\), the total can reach approximately \(2 \times 10^{14}\). In Python, you don’t need to worry about integer overflow, but in other languages, you need to use 64-bit integer types.

Source Code

def solve():
    N, K = map(int, input().split())
    
    # For each product, calculate the discount when using a coupon
    # Discount = A_i - B_i
    discounts = []
    total_normal = 0
    
    for _ in range(N):
        A, B = map(int, input().split())
        total_normal += A
        discounts.append(A - B)
    
    # Sort by discount in descending order and select top K
    discounts.sort(reverse=True)
    
    # Calculate the sum of top K discounts
    total_discount = sum(discounts[:K])
    
    # Minimum purchase amount = Total regular price - Sum of selected discounts
    print(total_normal - total_discount)

solve()

---

This editorial was generated by claude4.5opus.