Overview

Given the regular price and sale price of each product, the problem asks to minimize the total purchase amount by using discount coupons on at most \(K\) products.

Analysis

For each product, consider the “savings” from using a coupon — this is simply the difference \(A_i - B_i\) between the regular price \(A_i\) and the sale price \(B_i\). In other words, by using coupons on products with the largest differences, we can maximize the total reduction in payment.

Therefore, the optimal strategy is to assume all products are bought at their regular prices, compute the total, and then subtract the maximum possible discount obtained by using coupons.

A naive approach would be to “try using coupons on every subset of products (of size at most \(K\)) and compute the total,” but this takes exponential time and is impractical.

Instead, we compute all differences \(A_i - B_i\), sort them in descending order, and use coupons on the top \(K\) products. This allows us to efficiently obtain the maximum savings.

Algorithm

1. Compute the total of all regular prices: \(total = \sum_{i=1}^{N} A_i\).
2. Compute the price difference \(diff_i = A_i - B_i\) for each product and store them in a list.
3. Sort this list in descending order.
4. Compute the sum of the top \(K\) differences: \(discount = \sum_{i=0}^{K-1} diff_i\) (maximum savings from coupons).
5. The final answer is \(total - discount\).

Example

Sample input:

3 2
5 3
8 4
6 5

• Total of regular prices: \(5 + 8 + 6 = 19\)
• Price differences: \([2, 4, 1]\)
• After sorting (descending): \([4, 2, 1]\)
• Sum of top \(K=2\): \(4 + 2 = 6\)
• Amount after savings: \(19 - 6 = 13\)

Complexity

• Time complexity: \(O(N \log N)\) (dominated by sorting)
• Space complexity: \(O(N)\) (array to store price differences)

Implementation Notes

• Uses sys.stdin.read for fast input processing (a countermeasure for Python’s slow standard input).
• When sorting the difference list, reverse=True is specified to sort in descending order.
• Works correctly even when the number of available coupons is \(K=0\) (sum on an empty list returns 0).

## Source Code

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    
    products = []
    total = 0
    diffs = []
    
    index = 2
    for _ in range(N):
        A = int(data[index])
        B = int(data[index+1])
        total += A
        diffs.append(A - B)
        index += 2
    
    diffs.sort(reverse=True)
    
    discount = sum(diffs[:K])
    
    result = total - discount
    print(result)

if __name__ == "__main__":
    main()

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