通天之分组背包(Grouped Knapsack)

题目描述

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

输入格式

两个数 $m,n$，表示一共有 $n$ 件物品，背包能承受的最大重量为 $m$。

接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。

输出格式

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

样例输入 #1

45 3
10 10 1
10 5 1
50 400 2

样例输出 #1

10

数据范围

对于 $100\%$ 的数据，$0 \le m \le 1000$，$1 \le n \le 1000$，$1 \le k \le 100$，$a_i, b_i$ 为非负整数且 $0 \le c_i \le 10^4$。

知识点与难度

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1200。

测试点分布

出处：原题链接