← 返回题单
题单练习 动态规划基础
← 上一题 下一题 →

A5042 | 礼物

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小 $P$ 和小 $M$ 在逛一家纪念品店。纪念品店里一共有 $n$ 种商品，第 $i$ 种商品的价格为 $c_i$ 元，可以提供 $v_i$ 单位的幸福度，商店里每种商品都有无数件，他们的预算是 $m$ 元。小 $M$ 每次会挑选两件不同种类的商品买下，而小 $P$ 总是会收下其中幸福度最低的一件。
他们可能会购买多次，小 $M$ 想知道，在预算之内小 $P$ 获得的幸福度最大是多少。

输入格式

输入的第一行包含两个正整数 $n, m$，表示商品数量与他们的预算。

接下来 $n$ 行，第 $i$ 行包含两个正整数 $c_i, v_i$，表示一件商品的价格与幸福度。

输出格式

输出的唯一一行包含一个整数，小 P 可能获得的最大幸福度.

输入输出样例

输入 #1
5 5
1 2
2 3
1 3
2 4
5 5
输出 #1
5
输入 #2
10 10
1 10
9 5
1 4
9 3
7 7
10 2
5 3
5 2
1 1
1 10
输出 #2
50
C++ 编辑器
输入
输出