Happy Christmas

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 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
© 2015 HUST ACMICPC TEAM. All Right Reserved.