自 01 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
自 01 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 01 背包，他的物品大致可分为k组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。
两个数m,n，表示一共有n件物品，背包能承受的最大重量为m。 接下来n行，每行 3 个数a_i,b_i,c_i，表示物品的重量，利用价值，所属组数。
一个数，最大的利用价值。
45 3 10 10 1 10 5 1 50 400 2
10
0≤m≤1000，1≤n≤1000，1≤k≤100，0≤a_i,b_i,c_i≤10000
luogu