D. 通天之分组背包

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

两个数 $m,n$ ，表示一共有 $n$ 件物品，总重量为 $m$ 。

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

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

$0 \leq m \leq 1000$ ， $1 \leq n \leq 1000$ ， $1\leq k\leq 100$ ， $a_i, b_i, c_i$ 在 int 范围内。