Problem 1058 --A. 买零食

1058: A. 买零食

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 574  Solved: 91
[Submit][Status][Web Board][Creator:]

Description

Kajitsu最喜欢吃零食了。

已知超市里面有n种零食,每种零食有且只有一包。第i种零食价格为w[i]可以给Kajitsu带来v[i]点快乐值。

现在Kajitsu手上有m元钱,他想知道他最多能获得多少快乐值。

Input

第一行有两个数字 n,m ,用空格隔开

之后n行,第i+1行为两个数字w[i] v[i],用空格隔开

n≤100,m≤104,0≤v[i]≤100

表达式涵义如题意所示

Output

输出为一行,最大快乐值

Sample Input

3 70
71 100
69 1
1 2

Sample Output

3

HINT

Source

[Submit][Status]