#ABC229C. 芝士
芝士
AT_abc229_c [ABC229C] Cheese
题目描述
高桥君在披萨店工作,打算作为员工餐做一份美味的芝士披萨。
现在,高桥君面前有 种芝士。第 种芝士每 克的美味度为 ,共有 克。
披萨的美味度由放在披萨上的芝士美味度总和决定。但是,如果用太多芝士会被批评,因此放在披萨上的芝士总重量必须不超过 克。
在这个条件下,请求出披萨可能达到的最大美味度。
输入格式
第一行输入两个整数 $n, w \left(1 \leqq n \leqq 3 \times 10^5;\ 1 \leqq w \leqq 3 \times 10^8\right)$ 代表芝士的种类数和放在披萨上的芝士总重量上限。
此后 行,第 行输入两个整数 $a_i, b_i \left(1 \leqq a_i \leqq 10^9;\ 1 \leqq b_i \leqq 1000\right)$ 代表第 种芝士每 克的美味度和这种芝士的总重量。
输出格式
在一行上输出一个整数,代表披萨可能达到的最大美味度。
测试样例
3 5
3 1
4 2
2 3
15
样例 1 解释
最优方案是第 种芝士取 克、第 种芝士取 克、第 种芝士取 克。此时芝士总重量为 克,披萨的美味度为 。
4 100
6 2
1 5
3 9
8 7
100
样例 2 解释
所有芝士的总重量为 克,不足 克,因此可以把全部芝士都放在披萨上,此时披萨的美味度为 。
10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291
2357689932073
数据范围与提示
所有输入均为整数。
由 ChatGPT 4.1 翻译