题目描述

一个旅行者有一个最多能装 $V$ 公斤的背包，现在有 $n$ 件物品，它们的重量分别是 $W_1, W_2, \dots, W_n$，它们的价值分别为 $C_1, C_2, \dots, C_n$。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

输入格式

第一行三个整数 $V, N, T$，分别表示背包容量、物品数量和最大组号。

接下来 $N$ 行，每行三个整数 $W_i, C_i, P$，分别表示第 $i$ 件物品的重量、价值和所属组号。

输出格式

一行一个整数，表示最大总价值。

样例

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

20

提示

样例解释

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

数据范围

• $1 \le V \le 200$
• $1 \le N \le 30$
• $1 \le T \le 10$
• $1 \le W_i, C_i \le 100$
• 每组至少有一件物品，组号 $P$ 满足 $1 \le P \le T$