Problem G: ala的杂货店(开店第一天)

Problem G: ala的杂货店(开店第一天)

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 204  Solved: 64
[Submit] [Status] [Web Board] [Creator:]

Description

ala的杂货店终于开张了!开张的第一天,dzl听说了这个消息就带着m元钱前来捧场,ala拿出了他精心准备的n件物品,每件物品有一个实用值和对应的价格,dzl想在m元钱内买到实用值最多的物品组合。dzl灵光一闪,说这不是XX问题嘛,ala撇撇嘴,说那你别用XX啊。dzl为难了,想让你帮他解决这个问题。

Input

数据为单组
数据的第一行有两个整数,分别为n件物品和m元钱(1<=n<=15,1<=m<=1000)
第i+1行为第i件物品的实用值c[i]和价格w[i]元(1<=c[i],w[i]<=1000)

Output

输出一行为可以得到的最大的实用值。

Sample Input Copy

5 10
1 5
2 4
3 3
4 2
5 1

Sample Output Copy

14