题目描述

黑猫老师暑假打算去郊游，需要整理很多物品，将物品分为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

提示

1≤m,n≤1000，

1≤k≤100，

1≤$a_i,b_i$≤5000，

1≤$c_i$≤100。