1546: 【提高】吃鱼 (fish)

内存限制:16 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:2 通过:2

题目描述

小花爱吃鱼,这是全世界都知道的事情。它的好朋友编程兔给它准备了很多的零食,每一样都是小花喜欢的。当然了,里面最多的肯定是鱼。某一天编程兔给小花准备了两种鱼,一种鱼的重量是 1,另一种鱼的重量是 2,重量为 1 的鱼有不同的美味值,重量为 2 的鱼也有不同的美味值。现在假设小花的胃口最多能吃下不超过重量为 v 的鱼,小花希望吃掉的鱼的美味值总和最大。

输入格式

输入数据第一行是两个正整数 n 和 v,n 表示鱼的数量,v 表示小花的胃口。接下来 n 行,每行两个正整数,第一个正整数表示鱼的重量(只有 1 和 2 两种可能),另一个正整数表示这条的美味值。

输出格式

输出只有一行一个整数,表示小花能得到的最大美味值总和。

输入样例 复制

3 2 
1 2 
2 7 
1 3

输出样例 复制

7

数据范围与提示

小花选择了第 2 条鱼吃,美味值是 7。

数据规模: :

对于 60%的数据,1<=n<=2000。

对于 100%的数据,1<=n<=30000,1<=v<=60000,每条鱼的美味值不超过 10000。


来源:

【2019常州市天宁区选拔赛】