题目描述

有一个最大承重为 $V$ 的背包，现有 $N$ 件物品，每件物品有对应的重量 $w_i$、价值 $c_i$。所有物品被划分为 $T$ 个互斥的组，每组物品最多有10个，同一组内的物品最多只能选择一件装入背包。请你选择若干物品装入背包，在总重量不超过背包最大承重的前提下，使得装入物品的总价值最大。

输入格式

第一行三个整数 $V$、$T$、$N$，分别表示背包的最大承重、物品的总组数、物品的总数量。 接下来 $N$ 行，每行三个整数 $w_i$、$c_i$、$p_i$，依次表示第 $i$ 件物品的重量、价值，以及它所属的组号。保证所有组号均在 $1 \sim T$ 范围内。

输出格式

仅输出一行一个整数，表示可获得的最大总价值。

样例 #1

样例输入 #1

10 3 6
2 1 1
3 3 1
4 8 2
6 9 2
2 8 3
3 9 3

样例输出 #1

20

样例解释 #1

本题共有3组物品，第1组包含2件物品，第2组包含2件物品，第3组包含2件物品。背包最大承重为10。 最优方案为：从第1组选择重量3、价值3的物品，第2组选择重量4、价值8的物品，第3组选择重量3、价值9的物品。总重量为 $3+4+3=10$，总价值为 $3+8+9=20$，符合背包承重限制，且为可获得的最大价值。

数据范围与提示

对于 $100\%$ 的数据，满足： $1 \le V \le 1000$，$1 \le T \le 3 \times 10^4$，$1 \le N \le 1 \times 10^5$，$1 \le w_i \le V$，$1 \le c_i \le 1000$。