问题描述

有 $N$ 件物品和一个体积为 $M$ 的背包。第 $i$ 个物品的体积为 $v_i$，价值为 $w_i$。每件物品只能使用 $c_i$ 次。

请问可以通过什么样的方式选择物品，使得物品总体积不超过 $M$ 的情况下总价值最大，输出这个最大价值即可。

输入格式

第一行输入两个正整数 $N,M$。$(1\le N,M\le 100)$

接下来 $N$ 行，每行输入三个整数 $v_i,w_i,c_i$。$(0\le v_i,w_i,c_i\le 100)$

输出格式

输出一个整数，表示符合题目要求的最大价值。

样例输入

4 5
1 2 3
2 4 1
3 4 3
4 5 2

样例输出

10