Time Limit: 3000 ms
Memory Limit: 65535 ms
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?
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)
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.