时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(N\) 个物品，其中第 \(i\) 种物品的体积为 \(v[i]\)、价值为 \(p[i]\)。这些物品被分成了若干组，每组内的物品互相冲突，你最多只能选择其中的一个。那么你应该那些一些物品装入一个容量为 \(C\) 的背包，才能使背包内的物品价值和最大。

【输入格式】

　　第 1 行是整数 \(n、C\) 和 \(T\)，表示有 \(n\) 个物品，背包的容量为 \(C\)，物品组数 \(T\)。
　　接下来的 \(n\) 行，每行三个整数：\(v[i]、p[i]\) 和 \(z[i]\)，表示物品i的体积、价值和所属的组号。

【输出格式】

　　一个整数，表示能得到的最大价值。

【输入输出样例】

　Input

6 10 3
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

　Output

20

【数据限制】

　　\(1≤N≤100\)
　　\(1≤v[i],C≤100000\)
　　\(1≤p[i]≤1000000\)

【来源】

　　Mr.he