102292: [AtCoder]ABC229 C - Cheese
Description
Score : $300$ points
Problem Statement
Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are $N$ kinds of cheese in front of him.
The deliciousness of the $i$-th kind of cheese is $A_i$ per gram, and $B_i$ grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most $W$ grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.
Constraints
- All values in input are integers.
- $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$
Input
Input is given from Standard Input in the following format:
$N$ $W$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$
Output
Print the answer as an integer.
Sample Input 1
3 5 3 1 4 2 2 3
Sample Output 1
15
The optimal choice is to use $1$ gram of cheese of the first kind, $2$ grams of the second kind, and $2$ grams of the third kind.
The pizza will have a deliciousness of $15$.
Sample Input 2
4 100 6 2 1 5 3 9 8 7
Sample Output 2
100
There may be less than $W$ grams of cheese in total.
Sample Input 3
10 3141 314944731 649 140276783 228 578012421 809 878510647 519 925326537 943 337666726 611 879137070 306 87808915 39 756059990 244 228622672 291
Sample Output 3
2357689932073
Input
题意翻译
有 $N$ 种奶酪,总共 $W$ 克。 每种奶酪放在披萨上能提升 $A_i$的美味度,但是最多放$B_i$克。 求能产生的最大美味度。Output
得分: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