1417 - Happy Christmas

Time Limit: 1s Memory Limit: 128MB

Submissions: 226 Solved: 83
Description

Christmas is coming and our lucky xiaoY will get a lot of gifts. But his mother is very strict to him, she don’t want xiaoY get that much of gifts. So he give xiaoY a gift bag and told xiaoY that he can just choose some of the gifts to fulfill this bag. Because xiaoY’s evil bag is damn small, he have to decide carefully witch gifts he want!

Suppose xiaoY has preference ai of gift i, and the volume of gift i is bi. You just need to tell xiaoY the maximum preference he can get! (We assume bag’s volume is M)

Input

Multiple cases:

N, M (N---the number of gifts xiaoY received, M-----bag’s volume) (N<1000 and M<10000)

N line followed

ai bi

0 0 indicates the end of input

Output

T ------- Maximum preference xiaoY can get

Sample Input
3 2
2 1
3 1
4 1
0 0
Sample Output
7
Hint

3 + 4 = 7 (choose 2 and 3 gift is the best idea!)

Source
He Jian, HUST Campus 2010, Preliminary