通天之分组背包

题目背景

直达通天路·小A历险记第二篇

题目描述

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

输入输出格式

输入格式


两个数m,n,表示一共有n件物品,总重量为m 接下来n行,每行3个数ai,bi,ci,表示物品的重量,利用价值,所属组数

输出格式


一个数,最大的利用价值

输入输出样例

输入样例 #1

45 3
10 10 1
10 5 1
50 400 2

输出样例 #1

10

说明

1<=m<=1000 1<=n<=1000 组数t<=100