配点 : $300$ 点

問題文

ピザ屋で働く高橋くんは、まかないとして美味しいチーズピザを作ることにしました。 今、高橋くんの目の前に $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$

出力

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

3 5
3 1
4 2
2 3

15

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

4 100
6 2
1 5
3 9
8 7

100

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

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

2357689932073