分组背包
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
题目描述
自 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 背包，他的物品大致可分为 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
输入格式
两个数 ，表示一共有 件物品，总重量为 。
接下来 行，每行 个数 ，表示物品的重量，利用价值，所属组数。
输出格式
一个数，最大的利用价值。
输入输出样例
输入 #1
45 3 10 10 1 10 5 1 50 400 2
输出 #1
10
说明/提示
,。