AT_abc229_c.[ABC229C] Cheese

入门

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君在披萨店工作，打算作为员工餐做一份美味的芝士披萨。
现在，高桥君面前有 $N$ 种芝士。
第 $i$ 种芝士每 $1$ 克的美味度为 $A_i$ ，共有 $B_i$ 克。
披萨的美味度由放在披萨上的芝士美味度总和决定。
但是，如果用太多芝士会被批评，因此放在披萨上的芝士总重量必须不超过 $W$ 克。
在这个条件下，请求出披萨可能达到的最大美味度。

输入格式

输入以如下格式从标准输入给出。

$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
```
输入#2
```
4 100
6 2
1 5
3 9
8 7
```
输出#2
```
100
```

输入#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

说明/提示

限制条件

所有输入均为整数。
$1 \leq N \leq 3 \times 10^5$
$1 \leq W \leq 3 \times 10^8$
$1 \leq A_i \leq 10^9$
$1 \leq B_i \leq 1000$

样例解释 1

最优方案是第 $1$ 种芝士取 $1$ 克，第 $2$ 种芝士取 $2$ 克，第 $3$ 种芝士取 $2$ 克。此时披萨的美味度为 $15$ 。

样例解释 2

也存在所有芝士的总重量不足 $W$ 克的情况。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页