题目描述

在一家披萨店工作的你正在为员工餐制作美味的奶酪披萨。

你的面前有 $N$ 种奶酪。

第 $i$ 种奶酪的美味程度为每克 $A_i$ ，而这种奶酪有 $B_i$ 克。

披萨的美味程度就是他放在披萨上面的奶酪的美味程度总和。

不过，奶酪放多了会惹老板生气，所以披萨上最多只能放 $W$ 克奶酪。

在此条件下，求披萨可能的最大美味度。

输入格式

第一行输入两个整数 $N,W$

接下来 $N$ 行每行两个整数 $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 解释

最佳选择是使用第一种奶酪 $1$ 克，第二种奶酪 $2$ 克，第三种奶酪 $2$ 克。

披萨的美味度为 $15$ 。

提示

• $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$