6683: 洛谷P1757 - 通天之分组背包
[Creator : ]
Description
自 $01$ 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 $01$ 背包，他的物品大致可分为 $k$ 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
Input
两个数 $m,n$，表示一共有 $n$ 件物品，总重量为 $m$。
接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。
接下来 $n$ 行，每行 $3$ 个数 $a_i,b_i,c_i$，表示物品的重量，利用价值，所属组数。
Output
一个数，最大的利用价值。
Constraints
$1 \leq m, n \leq 1000$。
Sample 1 Input
45 3
10 10 1
10 5 1
50 400 2
Sample 1 Output
10