题目描述

ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。
今、高橋くんの目の前に $N$ 種類のチーズがあります。
$i$ 種類目のチーズは $1$ [g] あたりのおいしさが $A_i$ で、 $B_i$ [g] あります。
ピザのおいしさは、ピザに乗せたチーズのおいしさの総和で決まります。
但し、チーズを使いすぎると怒られてしまうため、乗せたチーズの重さは合計で $W$ [g] 以下である必要があります。
この条件のもとで、可能なピザのおいしさの最大値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $W$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

答えを整数として出力せよ。

题目大意

有 $N$ 种奶酪，总共 $W$ 克。

每种奶酪放在披萨上能提升 $A_i$的美味度，但是最多放$B_i$克。

求能产生的最大美味度。

3 5
3 1
4 2
2 3

15

4 100
6 2
1 5
3 9
8 7

100

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

2357689932073

提示

制約

• 入力は全て整数
• $1\ \le\ N\ \le\ 3\ \times\ 10^5$
• $1\ \le\ W\ \le\ 3\ \times\ 10^8$
• $1\ \le\ A_i\ \le\ 10^9$
• $1\ \le\ B_i\ \le\ 1000$

Sample Explanation 1

$1$ 種類目のチーズを $1$ \[g\] 、 $2$ 種類目のチーズを $2$ \[g\] 、 $3$ 種類目のチーズを $2$ \[g\] 乗せるのが最適です。 このとき、ピザのおいしさは $15$ となります。

Sample Explanation 2

チーズの重量の総和が $W$ \[g\] に満たないケースもあります。