Children’s Day

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

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?

Input

Standard input contains several cases: in each case first line is three integers N, M, W (N<=50, M<=50, W<=1000). N is the amount of gifts in the shop. M is the largest number of gifts Kane can buy. W is the weight Kane’s father willing to buy gift. In the next N lines, each line gives you one gift’s information using three integers A, B, C (A<=1000, B<=1000). A means the gift’s price. B means the gift’s weight. C (either 0 or 1) means whether this gift is unique: 1 means you can only buy one of this gift, 0 means you can buy as many as possible. The last line of the file contains 0 0 0.

Output

For each case, you should just print the maximum of total money Kane’s farther will pay in one line.

Sample Input

2 3 100
15 15 0
65 60 1
2 3 100
40 40 0
60 65 1
0 0 0

Sample Output

95
80

Hint

Source

Cary

提交代码