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)

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

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

3 2
2 1
3 1
4 1
0 0

7

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