Overview

You purchase \(N\) items at either their “regular price” or “sale price.” Given the restriction that at most \(K\) items can be purchased at the sale price, the problem asks to minimize the total cost.

Analysis

The key to this problem is focusing on “how much cheaper it becomes by using a coupon” — that is, the discount amount.

1. Calculating the discount: For each item \(i\), let \(D_i = A_i - B_i\) be the difference between the regular price \(A_i\) and the sale price \(B_i\). This \(D_i\) represents “the amount saved by using a coupon on item \(i\).” Since the constraints guarantee \(A_i \geq B_i\), this value is always non-negative.
2. Rephrasing the problem: The goal of “minimizing the total cost” can be rephrased as: “Assume all items are purchased at regular price, then maximize the total discount by applying coupons.”
3. Applying a Greedy approach: It is most efficient to apply coupons to items with the largest discount \(D_i\) first. Since at most \(K\) coupons can be used, selecting the top \(K\) items with the largest discounts minimizes the overall purchase cost.

Algorithm

The solution is computed with the following steps:

1. Calculate the total cost total_a (\(\sum A_i\)) when all items are purchased at regular price.
2. Calculate the discount \(D_i = A_i - B_i\) for each item and store them in a list.
3. Sort the list of discounts in descending order (largest first).
4. Compute the sum max_savings of up to the first \(K\) elements from the sorted list.
5. total_a - max_savings is the desired minimum total cost.

Complexity

• Time complexity: \(O(N \log N)\)
  • Computing the discounts takes \(O(N)\), sorting takes \(O(N \log N)\), and summing the top \(K\) elements takes \(O(K)\). Overall, sorting is the dominant factor.
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used for the list storing the discounts.

Implementation Notes

• Fast I/O: When processing input of size \(N=2 \times 10^5\) in Python, reading all input at once with sys.stdin.read().split() is faster than calling input() repeatedly.

• Sort order: You can either use sort(reverse=True) to sort in descending order, or sort in ascending order and take the last \(K\) elements from the end, to select the items with the largest discounts.

• Using slicing: In Python, you can easily extract the top \(K\) elements using slicing like diffs[:k]. Even if \(K > N\), this does not cause an error — it simply returns all elements of the list, making it safe (although the constraints of this problem guarantee \(K \leq N\), this is a more general way of writing it).

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込み、スペースや改行で分割してリストにします
    # 競技プログラミングにおいて、大量の入力を高速に処理する一般的な手法です
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # イテレータを使用してデータを1つずつ取り出します
    it = iter(input_data)
    
    # N: 商品の個数, K: クーポンを使用できる最大個数
    n = int(next(it))
    k = int(next(it))
    
    total_a = 0
    diffs = [0] * n
    
    for i in range(n):
        a = int(next(it))
        b = int(next(it))
        # 全ての商品を通常価格で購入した場合の合計金額を計算
        total_a += a
        # 通常価格とセール価格の差（クーポンによる割引額）を計算
        # 制約より B_i <= A_i なので、この値は必ず0以上になります
        diffs[i] = a - b
        
    # 割引額が大きい順にソートします
    diffs.sort(reverse=True)
    
    # 最大でK個の商品にクーポンを適用できるため、
    # 割引額が大きい方から最大K個を選んで合計金額から差し引きます
    # スライス diffs[:k] は、kがリストの長さを超えても適切に処理されます
    max_savings = sum(diffs[:k])
    
    # 購入金額の合計の最小値を出力
    print(total_a - max_savings)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.