include [HTML_REMOVED]

const int maxn = 5e5 + 100;
typedef long long LL;

template [HTML_REMOVED]
inline void read(T &s) {
s = 0;
T w = 1, ch = getchar();
while (!isdigit(ch)) { if (ch == ‘-‘) w = -1; ch = getchar(); }
while (isdigit(ch)) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
s *= w;
}

int n;
int m;
int size;
int v[maxn];
int w[maxn];
int k[maxn];
int f[maxn];

int main()
{
size = 0;
read(n), read(m);
for (int i = 1, x, y, z, t; i <= n; i)
{
read(x), read(y), read(z);
if (z < 0)
{
w[size] = x;
v[size] = y;
k[size] = 1;
}
else if (z == 0)
{
w[size] = x;
v[size] = y;
k[size] = 0;
}
else if (z > 0)
{
t = 1;
while (t <= z)
{
w[size] = x * t;
v[size] = y * t;
k[size] = 1;
z -= t;
t <<= 1;
}
w[size] = x * z;
v[size] = y * z;
k[size] = 1;
}
}
f[0] = 0;
for (int i = 1; i <= size; i)
{
if (k[i])
for (int j = m; j >= w[i]; –j)
f[j] = std::max(f[j], f[j - w[i]] + v[i]);
else
for (int j = w[i]; j <= m; ++j)
f[j] = std::max(f[j], f[j - w[i]] + v[i]);
}
printf(“%d\n”, f[m]);
return 0;
}