← 返回题目列表

AtCoder · awc0003_c

C. 特价促销选择

中文机器翻译题面 查看原题

分数: 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