| 问题描述 |
|---|
有$$N$$件物品和一个容量为$$M$$的背包。 已知第$$i$$件物品的重量是$$w_i$$，价值是$$v_i$$，所属组号为$$k_i$$。（组号相同的物品至多选取一个） 求解如何选取物品才能使装入背包的物品价值总和最大。
|
| 输入描述 |
第一行是两个正整数$$M,N$$分别代表背包的容量和物品的件数。（$$1 \le M,N \le 1000$$） 接下来$$N$$行，每行三个整数$$w_i,v_i,k_i$$分别表示第$$i$$件物品的重量、价值和所属组号。（$$1 \le w_i,v_i,k_i \le 100$$）
|
| 输出描述 |
在一行中输出装入背包的物品价值总和的最大值。 |
| 样例输入复制样例 |
45 3 10 10 1 10 5 1 50 400 2 |
| 样例输出 |
10 |
| 相关 |