Fieldpack

Time Limit: 3000 ms

Memory Limit: 65535 ms

Description

Have you heard the 01 Bag Problem ? There is a bag,of which the weight is M.What's more,there are N kinds of foods, and the number of the ith kind of foods is c[i] and the weight of the ith foods is w[i]. Noting that same kind of foods have the same weight.We want to put foods into bag as much as possible so that the bag can be of full use.Can you tell me the maximun weight of foods we can put into bag?

Input

Multiple test cases.First line contains N and M, as for next N lines,each line contain a pair of integer,indicating w[i] and c[i]. (N < = 1000,M < = 10000,w[i] < = 1000,c[i] < = 1000)

Output

For each test cases,output only a singal integer, the maximun weight of foods we can put into bag. You can assume the answer can fit into 32-bit signed integer.

Sample Input

3 10
3 1
4 2
0 10

Sample Output

8

Hint

Source

崔嵬

提交代码