#include <bits/stdc++.h>
using namespace std;

int n, m, v[200005], w[200005], f[38005][38005];
int cnt = 0;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int x, y, k, jc = 1;
		cin >> y >> x >> k;
		while (k >= jc)
		{
			v[++cnt] = x * jc;
			w[cnt] = y * jc;
			k -= jc;
			jc *= 2;
			
		}
		if (k >= 1)
		{
			v[++cnt] = x * k;
			w[cnt] = y * k;
		}
	}	
	n = cnt;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			if (j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
			else f[i][j] = f[i - 1][j];
		}
	}
	cout << f[n][m];
	return 0;
}

上不去了，改大了变成MLE20分，改小了变成60MLE/60WA