D - 果樹園の収穫 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は広大な果樹園を経営しています。果樹園には N 本の果物の木があり、木 1, 木 2, \ldots, 木 N と番号が付けられています。それぞれの木からは複数回収穫することができます。

木 i（1 \leq i \leq N）は、初回の収穫で F_i 個の果物が採れますが、収穫を重ねるごとに木が疲弊し、採れる量が減っていきます。具体的には、木 i の疲弊度を D_i とすると、木 i から k 回目（k = 1, 2, 3, \ldots）に収穫したときに得られる果物の個数は \max(F_i - (k-1) \times D_i, \ 0) 個です。すなわち、同じ木から収穫するたびに疲弊度の分だけ収穫量が減少し、0 未満にはなりません。なお、ある木から何回目の収穫であるかはその木ごとに独立に数え、他の木の収穫状況には影響されません。

高橋君は、各木から何回ずつ収穫するかを自由に決めることができます。収穫しない木があっても構いません。ただし、収穫期間の制約により、すべての木に対する収穫回数の合計は M 回以下でなければなりません。異なる木からの収穫も、同じ木からの複数回の収穫も、すべて合わせて M 回以下です。なお、収穫量が 0 個となる収穫を行うことも許されますが、そのような収穫も 1 回として数えます。

このとき、得られる果物の個数の合計の最大値を求めてください。

制約

  • 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
  • 1 行目には、果物の木の本数を表す整数 N と、収穫できる合計回数の上限を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N 行にわたって、各果物の木の情報が与えられる。
  • 1 + i 行目（1 \leq i \leq N）には、木 i の初回収穫量 F_i と疲弊度 D_i が、スペース区切りで与えられる。

出力

高橋君が得られる果物の個数の合計の最大値を整数で 1 行に出力してください。

入力例 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

Score : 366 pts

Problem Statement

Takahashi manages a vast orchard. The orchard has N fruit trees, numbered Tree 1, Tree 2, \ldots, Tree N. Each tree can be harvested multiple times.

Tree i (1 \leq i \leq N) yields F_i fruits on the first harvest, but the tree becomes exhausted with each successive harvest, and the yield decreases. Specifically, if the exhaustion rate of tree i is D_i, then the number of fruits obtained from the k-th harvest (k = 1, 2, 3, \ldots) of tree i is \max(F_i - (k-1) \times D_i, \ 0). That is, each time the same tree is harvested, the yield decreases by the exhaustion rate, and it does not go below 0. Note that the harvest count for each tree is tracked independently, and is not affected by the harvest status of other trees.

Takahashi can freely decide how many times to harvest each tree. It is also fine to not harvest some trees at all. However, due to constraints on the harvesting period, the total number of harvests across all trees must be at most M. This includes harvests from different trees as well as multiple harvests from the same tree, all counted together toward the limit of M. Note that performing a harvest that yields 0 fruits is allowed, but such a harvest still counts as one harvest.

Find the maximum total number of fruits that can be obtained.

Constraints

  • 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
  • All inputs are integers

Input

N M
F_1 D_1
F_2 D_2
\vdots
F_N D_N
  • The first line contains the integer N representing the number of fruit trees and the integer M representing the upper limit on the total number of harvests, separated by a space.
  • The following N lines give the information for each fruit tree.
  • The (1 + i)-th line (1 \leq i \leq N) contains the initial harvest yield F_i and the exhaustion rate D_i of tree i, separated by a space.

Output

Print the maximum total number of fruits Takahashi can obtain, as an integer on a single line.

Sample Input 1

3 5
10 3
8 5
6 1

Sample Output 1

36

Sample Input 2

2 8
20 2
5 1

Sample Output 2

104

Sample Input 3

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

Sample Output 3

1000000495