题目描述

一个旅行者有一个最多能装 $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$，表示第 $i$ 件物品的重量、价值和所属组号。

输出格式

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

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

20

数据规模与约定

对于全部的测试点，保证 $0 \leq v \leq 200$, $0 \leq n \leq 30$, $1 \leq t \leq 10$，并且对于每个物品，$1 \leq p_i \leq t$，$w_i$ 和 $c_i$ 是非负整数。