通天之分组背包

题目背景

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

题目描述

小 A 最近沉迷背包问题。与经典的 0/1 背包不同，他发现自己这次面对的物品被划分为若干组，同一组内的物品彼此冲突——也就是说，每组最多只能选择一件（也可以整组都不选）。 请你计算：在不超过背包承重上限的前提下，所能获得的最大总价值。

输入格式

• 第一行包含两个整数 m, n：表示背包的最大承重为 m，共有 n 件物品。

• 接下来 n 行，每行三个整数 \(a_i, b_i, c_i\)，依次表示：

  • \(a_i\)：第 i 件物品的重量；
  • \(b_i\)：第 i 件物品的价值；
  • \(c_i\)：第 i 件物品所属的组号（同组物品互斥）。

注：组的总数 k 不直接给出，可由出现的组号 \(c_i\) 的取值范围确定。

输出格式

输出一个整数，表示在容量不超过 m 的条件下，最多能获得的总价值。

输入输出样例

输入

45 3
10 10 1
10 5 1
50 400 2

输出

10

样例说明 背包容量为 45。

• 第 3 件物品重量 50，放不下；
• 第 1、2 件物品同属第 1 组，二者不能同时选，应选价值更高的第 1 件（重 10、值 10）。 因此答案为 10。

说明/提示

• \(0 \le m \le 1000\)
• \(1 \le n \le 1000\)
• \(1 \le k \le 100\)（k 为组数）
• \(a_i, b_i, c_i\) 均在 int 范围内

解题要点（仅作提示） 这是典型的分组背包：每组内至多选一件。常见做法是对每组做一次"0/1 背包式"的转移（容量倒序枚举），用本组的所有物品尝试更新当前 dp 数组。