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