当前没有测试数据。

C - 奶酪

分数：300 分

问题描述

高桥在一家披萨店工作，他正在制作美味的奶酪披萨做员工餐。
他面前有 $N$ 种奶酪。
第 $i$ 种奶酪的美味度为每克 $A_i$，它有 $B_i$ 克。
披萨的美味度将取决于他在披萨上放的所有奶酪的美味度之和。
然而，使用太多奶酪会让他的老板生气，因此披萨上最多可以放 $W$ 克奶酪。
在这个条件下，找出披萨的最大可能美味度。

约束

• 输入中的所有值均为整数。
• $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 克， 第二种奶酪 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