AT_arc042_c.[ARC042C] おやつ

高桥君正在挑选要带去远足的零食。此次远足最多可以带总价为 $P$ 日元的零食。不过，班主任“けんしょう”老师很宽容，只要对于任意一种零食，如果去掉这一个零食后，剩下的零食总价不超过 $P$ 日元，那么就可以被允许。

例如，当最多可以带 $100$ 日元的零食时，如果带了价格分别为 $30$ 日元、$40$ 日元、$50$ 日元的零食，无论去掉哪一个零食，剩下的总价都不超过 $100$ 日元，因此老师会允许。但如果带了 $40$ 日元、$50$ 日元、$60$ 日元的零食，即使去掉 $40$ 日元的零食，剩下的总价也为 $110$ 日元，超过了 $100$ 日元，所以即使是宽容的老师也不会允许。

高桥君想带的零食有 $N$ 种，每种零食有价格和满足度。每种零食最多只能带一个。请在所有被老师允许的选择方式中，求出满足度总和最大的方案，并输出其满足度总和。

输入通过标准输入给出，格式如下：

$N$ $P$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_N$ $b_N$

• 第 $1$ 行包含两个整数 $N,\ P\ (1\leq N\leq 5000,\ 1\leq P\leq 5000)$，分别表示高桥君想带的零食种类数和零食总价的上限。
• 接下来的 $N$ 行，每行包含两个整数 $a_i,\ b_i\ (1\leq a_i\leq 100,\ 1\leq b_i\leq 100)$，分别表示第 $i$ 种零食的价格和满足度。

请输出在所有被老师允许的选择方式中，满足度总和最大的方案的满足度总和。

部分分

本题设置了部分分。

• 对于满足 $1\leq N\leq 100,\ 1\leq P\leq 100$ 的数据集，答对可获得 $50$ 分。

样例解释 1

选择第 $1$、第 $2$、第 $3$ 种零食时，满足度总和为 $190$，这是所有被老师允许的选择方式中最大的。

样例解释 3

该输入不包含在部分分范围内。

由 ChatGPT 4.1 翻译