分数: 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
输出
将答案打印为整数。
示例输入 1
3 5 3 1 4 2 2 3
示例输出 1
15
最佳选择是使用 1 第一类奶酪克, 2 第二种克,以及 2 克第三种。
披萨的美味 15.
示例输入 2
4 100 6 2 1 5 3 9 8 7
示例输出 2
100
可能少于 W 奶酪总克数。
示例输入 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