//单调队列优化多重背包问题
//优化思路 : 在f[i][j]中,只选择前i种物件的情况下
//将所有选择方法分类为 : 总体积为j, 并且对选择第i种物体的体积v[i]进行取模,得到一共v[i]个亮亮互斥的集合(0~v[i] - 1)类
//在相同的状态下(i相同), 所有种选法的最大体积不会超过v[i] * s[i]
//这样求最值就变成了 体积长度为v[i] * s[i]区间内,所有体积不超过j选法能取到的最大值
//于是在求解最值的时候优化成单调队列中的最值问题
//如以此来,多重背包问题的时间复杂度仅为O(mn)
#include<iostream>
using namespace std;
const int N = 1010, M = 20010;
int n, m;
int w[N], v[N], s[N];
int f[N][M];
int q[M];//q[i]代表在队列中的元素,从i到队尾tt所占据的体积之和
//q[hh]表示队列中所有元素一共占据的体积之和
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++) scanf("%d%d%d", &v[i], &w[i], &s[i]);
for(int i = 1; i <= n; i ++)
{
for(int r = 0; r < v[i]; r ++)//手动算出所有对v[i]取模的余数
{
int hh = 0, tt = -1;//初始化队头队尾
for(int j = r; j <= m; j += v[i])//遍历所有余数相同情况下,能取到的最大体积j
{
if(hh <= tt && j - q[hh] > v[i] * s[i]) hh ++;//判断能取到的最大体积下,减去目前队列中的体积.如果大于最大长度,则去掉队头
while(hh <= tt && f[i - 1][q[tt]] < f[i - 1][j] - ((j - q[tt]) / v[i] * w[i])) tt --;
//判断新加进来的最大值与队尾的最大值,直至找到第一个小于新插进来的数为止(单调队列)
//由于最大体积为j的状态比队头的状态要晚(j - q[hh]) / v[i]
//而且根据推导公式,每晚一个状态都比之前一个状态多w[i],于是将多的状态个数 - w[i]即可正确比较队头与新插进来的数
//
q[ ++ tt ] = j;
//每当使用的体积j变化1,状态的值便增加w[i]
f[i][j] = max(f[i][j], f[i - 1][q[hh]] + (j - q[hh]) / v[i] * w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}