g6-07986. 道具商店·同模型 未做

小杨在玩一款角色扮演游戏，想给角色堆攻击力：商店里有 $n$ 件道具，第 $i$ 件能提升 $a_i$ 点攻击力、售价 $c_i$ 枚金币，每件最多买一次。他现在有 $k$ 枚金币（$k$ 最多可达 $10^9$），其中 $a_i\le 500$、$n\le 500$，所有道具的攻击力总和不超过 $250000$。求他最多能提升多少点攻击力。

第一行两个整数 $n,k$。

接下来 $n$ 行，每行两个整数 $a_i,c_i$。

一行一个整数，表示最大攻击力提升。

输入 1

3 5
99 1
33 2
11 3

输出 1

132

买第 1、2 件：攻击力 $99+33=132$，金币 $1+2=3\le 5$。

$1\le n\le 500$，$1\le k\le 10^9$，$1\le a_i\le 500$，$1\le c_i\le 10^9$。

（与某道六级真题同模型，数据为自造。）