题目描述

Lucas 有一个背包，背包的容量为 $V$。

有 $n$ 件物品，第 $i$ 件物品的体积是 $c_i$，价值是 $w_i$，分组编号是 $g_i$。

同一个分组中最多只能选一件物品放入背包。

Lucas 想要将其中一些物品装入背包，并且在满足

• 装入背包的物品体积之和不超过 $V$

的情况下，

• 装入背包的物品价值之和最大。

求：最大价值。

输入格式

第一行，三个整数 $n$，$m$ 和 $V$，分别表示物品数量，分组数量，以及背包的容量。

接下来 $n$ 行，每行包含三个整数 $c_i$，$w_i$ 和 $g_i$，表示第 $i$ 件物品的体积和价值以及所属的分组编号。

输出格式

输出一个整数，表示放入背包的物品体积之和 $\le V$ 的情况下能够获得的最大价值。

样例

3 2 12
4 3 1
5 8 2
6 11 2

14

6 5 20
5 7 3
7 10 2
10 23 3
6 8 2
11 25 3
5 6 1

35

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n \le 20$，$c_i, w_i, V \le 2000$；
• 对于 $100\%$ 的数据，$1 \le m \le n \le 200$，$1 \le c_i, V \le 2 \cdot 10^6$，$1 \le w_i \le 10^9$，$1 \le p_i \le m$，可能存在某些分组中没有物品的情况。