← 返回题目列表

AtCoder · awc0050_b

B. 果园收获

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

分数: 333 分

问题陈述

高桥管理 N 果园。

果园 i (1 \le i \le N) 目前有 A_i 树上长着果实。

从明天开始,高桥将进行收割工作 K 天,正好选择 1 果园每天。他可以在多天内选择同一个果园,也可以选择具有以下特征的果园: 0 水果。

在果园进行收割工作时 i 一天内,高桥可以收获的水果数量等于该果园中当前剩余水果数量中较小的一个,并且 B_i。换句话说,如果有 r 工作前果园里剩下的水果,他收割了 \min(r, B_i) 水果,则剩余水果数量变为 r - \min(r, B_i).

没有新的果实生长,每个果园中的果实数量只会通过收获而减少。

当高桥最优地选择在哪些果园工作时 K 天,求他最多能收获的果实总数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 10^{18}
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 所有输入值均为整数

输入

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 在果园里 i 以及每天可收获的水果数量 B_i,用空格分隔。

输出

在一行上打印可以收获的最大水果总数。


示例输入 1

3 4
5 2
3 5
10 4

示例输出 1

13

示例输入 2

2 7
4 3
2 1

示例输出 2

6

示例输入 3

8 15
12 3
7 10
25 4
9 2
14 7
30 6
5 1
18 5

示例输出 3

82

示例输入 4

20 60
45 6
120 15
78 9
33 4
200 25
17 3
96 8
150 20
64 7
89 11
210 30
58 5
132 12
41 10
73 6
185 18
27 2
99 13
160 16
52 14

示例输出 4

1143

示例输入 5

1 1000000000000000000
1000000000 1000000000

示例输出 5

1000000000