题目描述

有 $n$ 种物品要放到一个袋子里，袋子的总容量为 $m$。第 $i$ 个物品属于第 $a_i$ 组，每组物品我们只能从中选择一个。第 $i$ 种物品的体积为 $v_i$，把它放进袋子里会获得 $w_i$ 的收益。问如何选择物品，使得在物品的总体积不超过 $m$ 的情况下，获得最大的收益？请求出最大收益。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行三个整数 $a_i,v_i,w_i$。

输出格式

一个整数，表示答案。

Samples

5 10
1 1 6
1 6 9
8 5 10
1 5 6
8 4 5

16

数据规模

对于所有数据保证 $1≤n,m,a_i,v_i,w_i≤1000$。