Cheese

题目描述

Takahashi，在一家披萨店工作，正在为员工餐制作一份美味的奶酪披萨。
他面前有 $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

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 \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$最优选择是使用第 1 种奶酪 $1$ 克，第 2 种奶酪 $2$ 克，第 3 种奶酪 $2$ 克。
披萨的美味度为 $15$。
奶酪总量可能少于 $W$ 克。

标签: AtCoder|abc229C

来源

AtCoder|abc229C