#ABC229C. 芝士

芝士

AT_abc229_c [ABC229C] Cheese

题目描述

\hspace{15pt}高桥君在披萨店工作,打算作为员工餐做一份美味的芝士披萨。

\hspace{15pt}现在,高桥君面前有 nn 种芝士。第 ii 种芝士每 11 克的美味度为 aia_i,共有 bib_i 克。

\hspace{15pt}披萨的美味度由放在披萨上的芝士美味度总和决定。但是,如果用太多芝士会被批评,因此放在披萨上的芝士总重量必须不超过 ww 克。

\hspace{15pt}在这个条件下,请求出披萨可能达到的最大美味度。

输入格式

\hspace{15pt}第一行输入两个整数 $n, w \left(1 \leqq n \leqq 3 \times 10^5;\ 1 \leqq w \leqq 3 \times 10^8\right)$ 代表芝士的种类数和放在披萨上的芝士总重量上限。

\hspace{15pt}此后 nn 行,第 ii 行输入两个整数 $a_i, b_i \left(1 \leqq a_i \leqq 10^9;\ 1 \leqq b_i \leqq 1000\right)$ 代表第 ii 种芝士每 11 克的美味度和这种芝士的总重量。

输出格式

\hspace{15pt}在一行上输出一个整数,代表披萨可能达到的最大美味度。

测试样例

3 5
3 1
4 2
2 3
15

样例 1 解释

\hspace{15pt}最优方案是第 11 种芝士取 11 克、第 22 种芝士取 22 克、第 33 种芝士取 22 克。此时芝士总重量为 1+2+2=51+2+2=5 克,披萨的美味度为 3×1+4×2+2×2=153 \times 1+4 \times 2+2 \times 2=15。

4 100
6 2
1 5
3 9
8 7
100

样例 2 解释

\hspace{15pt}所有芝士的总重量为 2+5+9+7=232+5+9+7=23 克,不足 w=100w=100 克,因此可以把全部芝士都放在披萨上,此时披萨的美味度为 6×2+1×5+3×9+8×7=1006 \times 2+1 \times 5+3 \times 9+8 \times 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

数据范围与提示

\hspace{15pt}所有输入均为整数。

\hspace{15pt}由 ChatGPT 4.1 翻译