芝士披萨

题目描述

在披萨店工作的高桥君正在为员工餐制作美味的芝士披萨。

他面前有 $N$ 种芝士。

第 $i$ 种芝士的美味度为每克 $A_i$,并且有 $B_i$ 克可用。

披萨的美味度等于放在披萨上的芝士的总美味度。

但是,芝士放太多会让老板生气,因此披萨上最多只能放 $W$ 克芝士。

在这个条件下,求披萨美味度的最大值。

输入格式

输入按以下格式从标准输入给出:

$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$ 克第一种芝士、$2$ 克第二种芝士和 $2$ 克第三种芝士。

披萨的美味度为 $15$。

4 100
6 2
1 5
3 9
8 7

100

芝士的总量可能不足 $W$ 克。

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$