题目描述

有 $n$ 种物品要放到一个袋子里，袋子的总载重量为 $m$，第 $i$ 种物品的重量为 $w_i$，把它放进袋子里会获得 $v_i$ 的收益，一共有 $c_i$ 个。问如何选择物品，使得在物品的总重量不超过 $m$ 的情况下，获得最大的收益？请求出最大收益。

输入格式

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

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

输出格式

一个整数，表示答案。

Samples

5 10
2 1 2
5 8 2
2 4 5
3 9 2
4 3 2

26

数据规模

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