2.4　分组背包问题

【题目描述】 分组背包问题（kbag）

物品大致可分为k（k≤100）组，同一组中的物品最多装一个，试求背包能装下的物品的最大价值。

【输入格式】

第一行为两个数m（0≤m≤1 000）和n（1≤n≤1 000），分别表示背包总承重和物品总数量。接下来的n行，每行有3个数a_i、b_i和c_i，分别表示物品的质量、价值和所属组数。

【输出格式】

输出一个数，即背包能装下的物品的最大价值。

【输入样例】

46 3

10 10 1

10 6 1

60 300 2

【输出样例】

10