儿童节

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

儿童节快到了,Kane请求他的父亲给他买一堆礼物。但是,他的父亲有点小气,父亲列举了2条规定:1.礼物的数量不得大于M2.礼物的总质量必须小于等于W。在商店里,每件礼物有它的价格和质量,另外,有些礼物是特殊的,顾客每次只能买1件同样的礼品。现在,Kane希望得到的礼物价格总和最大,你能帮助他吗?

Input

标准输入包括几个样例:每个样例的第一行给出3个整数N, M, W (N<=50, M<=50, W<=1000). N是在商店中礼物的种类数. M是爸爸规定的Kane所能买的礼物总数。W是爸爸规定的礼物总质量。在接下来的N行,每行给出3个整数A, B, C (A<=1000, B<=1000). A表示礼物的价格。B表示礼物的质量,C (0或1) 表示礼物是否特殊:1表示礼物只能买1件,0表示礼物能买任意件。输入最后以0 0 0结束。

Output

对于每个样例,只须在每一行输出Kane的父亲付出钱的最大值。

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

提交代码