P1176 - 通天之分组背包

内存限制：128 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：3 通过：2

01 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

两个数 m,n，表示一共有 n 件物品，总重量为 m。

接下来 n 行，每行 3 个数 ai,bi,ci，表示物品的重量，利用价值，所属组数。

一个数，最大的利用价值。

1 \leq m, n \leq 1000

。

1176: 通天之分组背包