分数: 300 分
问题陈述
高桥将购买全部 N 项,每项一项。
每个商品都有两个价格:“正常价格”和“促销价”。商品的正常价格 i (1 \leq i \leq N) is A_i 日元,售价为 B_i 日元。保证销售价格最多为正价,即 B_i \leq A_i.
高桥有一张特别折扣券。有了这张优惠券,他可以选择 最多 K 项目来自 N 物品并以促销价购买所选物品。其余未选择的商品将按正常价格购买。请注意,同一项目不能选择多次,也可以不选择任何项目(即选择 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
- 第一行包含一个整数 N 表示项目数和一个整数 K 代表可以以促销价购买的最大商品数量,以空格分隔。
- 以下 N 行各包含,对于 i第行 (1 \leq i \leq N),正常价格 A_i 和销售价格 项目的 B_i 项目数 i,用空格分隔。
输出
打印购买所有产品的最低可能总成本 N 项目作为单行上的整数。请注意,答案可能不适合 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