概要

各商品を「通常価格で買う」か「クーポンでセール価格にする」かを選び、クーポンを使える最大 \(K\) 個の範囲で合計金額を最小化します。

考察

クーポンを使うと、商品 \(i\) の支払いは \(A_i\) から \(B_i\) に下がります。つまり「いくら安くなるか」は
\(A_i - B_i\) 円です。

ここで重要な観察は次の通りです：

• まず全商品を通常価格で買うと合計は \(\sum A_i\)。
• そこから、クーポンを使った商品分だけ \((A_i - B_i)\) 円ずつ合計が減る。
• よって「合計を最小にする」ことは「値引き額 \((A_i - B_i)\) の合計を最大化する」ことと同値。

したがって、クーポンを使う商品は「値引き額が大きい順」に最大 \(K\) 個選ぶのが最適です。

素朴に「どの商品にクーポンを使うか」を全探索すると、選び方は最大で \(\binom{N}{K}\) 通りあり、\(N \le 2\times 10^5\) では到底間に合いません（TLE）。
この問題は各商品の効果（値引き額）が独立で、相互作用がないため、貪欲に大きい値引きから選べばよい、という形に落とし込めます。

例： - \((A,B)=(10,7),(8,3),(5,5)\)、\(K=2\) - 値引き額は \(3,5,0\) - 大きい順に \(5,3\) を選ぶ → 合計は \((10+8+5) - (5+3)=23-8=15\)

アルゴリズム

1. 合計 total を \(\sum A_i\) として計算する。
2. 各商品について値引き額 s = A_i - B_i を配列 savings に入れる。
3. savings を降順ソートする。
4. 上位 \(K\) 個の値引き額の合計 \(\sum_{j=1}^{K} savings[j]\) を total から引く。
5. total を出力する。
   （\(K=0\) のときは何も引かず、そのまま \(\sum A_i\)）

計算量

• 時間計算量: \(O(N \log N)\)（値引き額のソートが支配的）
• 空間計算量: \(O(N)\)（値引き額の配列）

実装のポイント

• \(A_i, B_i\) は最大 \(10^9\)、\(N\) は最大 \(2\times 10^5\) なので、合計は最大で約 \(2\times 10^{14}\) になります。Python なら整数は自動で大きくなるので安全ですが、他言語では 64bit 整数が必要です。

• savings.sort(reverse=True) で降順にし、sum(savings[:K]) で上位 \(K\) 個だけを足します。

• 入力が大きいので sys.stdin.readline を使うと安定します。

  ソースコード

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()

この解説は gpt-5.2-high によって生成されました。