Time Limit: 1000 ms
Memory Limit: 65535 ms
Children’s Day will come. Kane beg his father to buy a lot of gifts. But his father is a little mean. He makes 2 rules: 1.the number of all the gifts mustn’t larger than M; 2. the total weight of all the gifts chosen must smaller than W. In the shop, every gift has its price. What’s more, some gifts are particular; custom can only buy more one for each. Now, Kane problem is how to buy gifts so that the sum of gifts’ price is maximum. Could you help him?