← 返回题目列表

AtCoder · awc0008_d

D. 果园收获

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

分数: 366 分

问题陈述

高桥管理着一个巨大的果园。果园有 N 果树,编号树 1,树 2, \ldots,树 N。每棵树都可以多次采伐。

树 i (1 \leq i \leq N) 产量 F_i 在第一次收获时结出果实,但随着每次连续的收获,树变得精疲力尽,产量下降。具体来说,如果树的耗尽率 i is D_i,则从 k-次收获( 树的k = 1, 2, 3, \ldots) i is \max(F_i - (k-1) \times D_i, \ 0)。也就是说,每次采伐同一棵树时,产量都会按枯竭率减少,并且不会低于 0。请注意,每棵树的收获计数是独立跟踪的,并且不受其他树的收获状态的影响。

高桥可以自由决定每棵树收获多少次。完全不砍伐一些树木也很好。但由于采收期的限制, 所有树木的收获总数 最多必须是 M。这包括不同树木的收获以及同一棵树的多次收获,所有这些都计入限制 M。请注意,进行收获时会产生 0 水果是允许的,但这样的收获仍然算一次收获。

找出可以获得的最大水果总数。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq F_i \leq 10^9
  • 1 \leq D_i \leq 10^9
  • 所有输入均为整数

输入

N M
F_1 D_1
F_2 D_2
\vdots
F_N D_N
  • 第一行包含整数 N 代表果树的数量和整数 M 代表收获总数的上限,以空格分隔。
  • 以下 N 行给出了每棵果树的信息。
  • 的 (1 + i)- 第行 (1 \leq i \leq N) 包含初始收获产量 F_i 和耗尽率 树的 D_i 树的 i,用空格分隔。

输出

在一行中以整数形式打印高桥可以获得的最大水果总数。


示例输入 1

3 5
10 3
8 5
6 1

示例输出 1

36

示例输入 2

2 8
20 2
5 1

示例输出 2

104

示例输入 3

5 10
100 30
50 10
80 25
1000000000 1000000000
30 5

示例输出 3

1000000495