問題文

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

制約

• 入力は全て整数
• $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$

入力

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

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

出力

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

入力例 1

3 5
3 1
4 2
2 3

出力例 1

15

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

入力例 2

4 100
6 2
1 5
3 9
8 7

出力例 2

100

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

入力例 3

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

出力例 3

2357689932073