← 返回题目列表

AtCoder · abc229_c

F. 奶酪

中文机器翻译题面 查看原题

分数: 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