84435 - 通天之分组背包
时间限制 : 1 秒
内存限制 : 128 MB
自 01 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为 k 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
输入
两个数m,n，表示一共有n件物品，背包能承受的最大重量为m。 接下来n行，每行 3 个数a_i,b_i,c_i，表示物品的重量，利用价值，所属组数。
输出
一个数，最大的利用价值。
样例
输入
45 3 10 10 1 10 5 1 50 400 2
输出
10
提示
0≤m≤1000，1≤n≤1000，1≤k≤100，0≤c_i≤10000
来源
lougu