题目背景

:::info[管理员备注]{open} 本题数据实际满足 $a_i,b_i$ 为非负整数，且 $0\le c_i\le 10^4$。鉴于此题为分组背包经典例题，不会加入 $a_i,b_i,c_i$ 为负数之类的无意义的 hack 数据。 :::

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

题目描述

自 $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 \leq m \leq 1000$，$1 \leq n \leq 1000$，$1\leq k\leq 100$，$a_i, b_i, c_i$ 在 int 范围内。

GESPOJ 可见测试数据

以下数据是本题实际评测数据的一部分。

1 1
308 3334 1

0

349 22
131 8424 4
72 8195 5
358 2453 4
379 9578 8
82 6686 3
426 8551 6
512 6489 6
415 2217 3
738 9533 1
56 6502 5
518 9659 7
490 878 8
632 4422 5
397 514 4
597 3946 7
292 2811 2
219 9109 8
20 9856 6
17 310 8
39 7975 1
903 5637 4
780 9817 6

41136