B - 果樹園の収穫 解説 /

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

配点 : 333 点

問題文

高橋君は N 個の果樹園を管理しています。

果樹園 i (1 \le i \le N) には現在 A_i 個の果物が実っています。

高橋君は、明日から K 日間、毎日ちょうど 1 つの果樹園を選んで収穫作業を行います。同じ果樹園を複数の日に選ぶこともでき、果物が 0 個の果樹園を選ぶことも許されます。

果樹園 i で 1 日収穫作業を行うと、その果樹園に現在残っている果物の数と 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

1 行目には、果樹園の数 N と作業日数 K がスペース区切りで与えられます。

続く N 行のうち i 行目 (1 \leq i \leq N) には、果樹園 i の果物の数 A_i と 1 日あたりの収穫可能数 B_i がスペース区切りで与えられます。

出力

収穫できる果物の個数の合計の最大値を 1 行で出力してください。

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

Score : 333 pts

Problem Statement

Takahashi manages N orchards.

Orchard i (1 \le i \le N) currently has A_i fruits growing on its trees.

Starting from tomorrow, Takahashi will perform harvesting work over K days, choosing exactly 1 orchard each day. He may choose the same orchard on multiple days, and he is also allowed to choose an orchard with 0 fruits.

When harvesting work is performed at orchard i for one day, Takahashi can harvest a number of fruits equal to the smaller of the number of fruits currently remaining in that orchard and B_i. In other words, if there are r fruits remaining in the orchard before the work, he harvests \min(r, B_i) fruits, and the remaining number of fruits becomes r - \min(r, B_i).

No new fruits grow, and the number of fruits in each orchard only decreases through harvesting.

When Takahashi optimally chooses which orchards to work at over the K days, find the maximum total number of fruits he can harvest.

Constraints

  • 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)
  • All input values are integers

Input

N K
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains the number of orchards N and the number of work days K, separated by a space.

The following N lines, where the i-th line (1 \leq i \leq N), contain the number of fruits A_i in orchard i and the number of fruits harvestable per day B_i, separated by a space.

Output

Print the maximum total number of fruits that can be harvested, on a single line.

Sample Input 1

3 4
5 2
3 5
10 4

Sample Output 1

13

Sample Input 2

2 7
4 3
2 1

Sample Output 2

6

Sample Input 3

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

Sample Output 3

82

Sample Input 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

Sample Output 4

1143

Sample Input 5

1 1000000000000000000
1000000000 1000000000

Sample Output 5

1000000000