/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、 N 個の商品をすべて1個ずつ購入します。
各商品には「通常価格」と「セール価格」の2つの価格が設定されています。商品 i (1 \leq i \leq N) の通常価格は A_i 円、セール価格は B_i 円です。セール価格は通常価格以下であること、すなわち B_i \leq A_i が保証されています。
高橋君は特別な割引クーポンを1枚持っています。このクーポンにより、 N 個の商品の中から K 個以下 の商品を選んで、選んだ商品をセール価格で購入することができます。選ばなかった残りの商品は通常価格で購入します。なお、1つの商品を複数回選ぶことはできず、1個も選ばない（0 個選ぶ）こともできます。
高橋君がセール価格で購入する商品の選び方を最適にしたとき、 N 個の商品の購入金額の合計の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq B_i \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
- 1 行目には、商品の個数を表す整数 N と、セール価格で購入できる商品数の上限を表す整数 K が、スペース区切りで与えられる。
- 続く N 行のうち i 行目 (1 \leq i \leq N) には、商品 i の通常価格 A_i とセール価格 B_i が、スペース区切りで与えられる。
出力
N 個の商品の購入金額の合計の最小値を整数で 1 行に出力せよ。なお、答えは 32 ビット整数の範囲に収まるとは限らないことに注意せよ。
入力例 1
3 2 100 80 200 150 300 250
出力例 1
500
入力例 2
5 3 1000 500 800 800 600 400 900 700 1200 300
出力例 2
2900
入力例 3
7 4 500000000 100000000 300000000 250000000 800000000 200000000 150000000 150000000 600000000 350000000 400000000 100000000 700000000 650000000
出力例 3
1900000000
Score : 300 pts
Problem Statement
Takahashi will purchase all N items, one of each.
Each item has two prices: a "regular price" and a "sale price." The regular price of item i (1 \leq i \leq N) is A_i yen, and the sale price is B_i yen. It is guaranteed that the sale price is at most the regular price, that is, B_i \leq A_i.
Takahashi has one special discount coupon. With this coupon, he can choose at most K items from the N items and purchase the chosen items at their sale prices. The remaining items that are not chosen will be purchased at their regular prices. Note that the same item cannot be chosen more than once, and it is also allowed to choose no items (i.e., choose 0 items).
When Takahashi optimally chooses which items to purchase at the sale price, find the minimum possible total cost of purchasing all N items.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq N
- 1 \leq B_i \leq A_i \leq 10^9
- All input values are integers.
Input
N K A_1 B_1 A_2 B_2 \vdots A_N B_N
- The first line contains an integer N representing the number of items and an integer K representing the maximum number of items that can be purchased at the sale price, separated by a space.
- The following N lines each contain, for the i-th line (1 \leq i \leq N), the regular price A_i and the sale price B_i of item i, separated by a space.
Output
Print the minimum possible total cost of purchasing all N items as an integer on a single line. Note that the answer may not fit within a 32-bit integer.
Sample Input 1
3 2 100 80 200 150 300 250
Sample Output 1
500
Sample Input 2
5 3 1000 500 800 800 600 400 900 700 1200 300
Sample Output 2
2900
Sample Input 3
7 4 500000000 100000000 300000000 250000000 800000000 200000000 150000000 150000000 600000000 350000000 400000000 100000000 700000000 650000000
Sample Output 3
1900000000