#1996. 分组背包

分组背包

题目描述

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

输入格式

两个数 m,nm,n,表示一共有 nn 件物品,总重量为 mm

接下来 nn 行,每行 33 个数 ai,bi,cia_i,b_i,c_i,表示物品的重量,利用价值,所属组数。

输出格式

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

样例 #1

样例输入 #1

45 3
10 10 1
10 5 1
50 400 2

样例输出 #1

10

提示

1m,n10001 \leq m, n \leq 10001k1001\leq k\leq 100ai,bi,cia_i, b_i, c_iint 范围内。