有许多物品,分作$K$组。有一个容量为$C$的背包。现在所有物品中，最多选择$K$件物品放入背包。每一个分组中，最多只能选择一件物品。放入第$i$件物品耗费的空间是$w_i$得到的价值是$v_i$。求解在不超过容量的前提下，将哪些物品装入背包可使价值总和最大。

第一行为两个正整数$N、C和K$，$N$表示物品数量，$C$表示背包容量，$K$表示最大的组编号。

第2行至第N+1行，每行为三个正整数$w_i,v_i,k_i$，表示第$i$个物品的重量、价值和分组。

放入背包的最大价值。

对100%的数据，$1 \leq N\leq 500,1 \leq C \leq 10000,1\leq K \leq 100$.