题目背景

2025 年 12 月 GESP C++ 六级编程第 2 题

题目描述

道具商店里有 $n$ 件道具可供挑选。第 $i$ 件道具可为玩家提升 $a_i$ 点攻击力，需要 $c_i$ 枚金币才能购买，每件道具只能购买一次。现在你有 $k$ 枚金币，请问最多可以提升多少点攻击力？

输入格式

第一行输入两个正整数 $n,k$，表示道具数量以及金币数量。

接下来 $n$ 行，每行输入两个正整数 $a_i,c_i$，表示道具提升的攻击力和购买所需金币。

输出格式

输出一行一个整数，表示最多可以提升的攻击力点数。

3 5
99 1
33 2
11 3

132

数据范围与提示

• 对于 $60$ 的测试点，$1 \le k\le 500$，$1 \le c_i \le 500$
• 对于所有测试点，$1 \le n\le 500$，$1 \le k\le 10^9$，$1 \le a_i \le 500$，$1 \le c_i \le 10^9$

若输入为：

4 100 10 1 20 11 40 33 100 99

输出为：

110