1546 - 小鱼干
题目描述
小鱼干是小花猫最爱的食物。
小美为小花猫买了 n 包不同味道的小鱼干，这 n 包小鱼干只有 2 种不同重量的包装：1 KG 和 2 KG。
每一包小鱼干都标注了这包小鱼干吃完，小花猫可以获得的能量值。
小花猫一次最多只能吃掉 maxw KG 小鱼干，请编程计算出小花猫一次吃小鱼干能获得的最大能量值。
请注意：每一包小鱼干小花猫会选择一次吃掉，或者不吃，不会出现拆开吃一部分的情况。
输入
第一行有两个正整数 n 和 maxw；
接下来 n 行，每行两个正整数，第一个正整数表示这包小鱼干的重量，另一个正整数表示这包小鱼干的能量值。
输出
输出只有一行一个整数，表示小花能获得的最大能量值。
样例
输入
3 2 1 2 2 7 1 3
输出
7
输入
12 5 2 5115 2 853 1 113 2 6307 1 863 1 5804 2 9927 2 1561 2 399 2 4530 2 2557 1 2471
输出
22038
说明
【样例说明】
小花猫选择了第 2 条鱼，能获得最大的能量值为 7。
【数据规模】
对于 60\% 的数据，1 \le n \le 2000。
对于 100\% 的数据，1 \le n \le 30000,1 \le v \le 60000，每条鱼的美味值不超过 10000。
来源
区赛
标签
