#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int N; // Số loại vật liệu
ll W; // Sức chứa của balo (trọng lượng tối đa)
cin >> N >> W;
// Mảng dp[j] lưu giá trị tối đa khi cân nặng chính xác là j
vector<ll> dp(W+1, 0);
// Duyệt qua từng loại vật liệu
for(int i = 0; i < N; i++) {
ll w, v, k;
cin >> k >> w >> v; // Đọc số lượng k, trọng số w, giá trị v của loại vật i
// Nếu một vật chiếm trọng lượng 0 và có giá trị dương, ta có thể lặp vô hạn.
// Tuy nhiên, nếu w = 0 nhưng v <= 0 hoặc dp không đổi, ta bỏ qua luôn.
if (w == 0) continue;
// Nếu K rất lớn: đủ để lấp đầy mọi trọng số, coi như knapsack không giới hạn
if (k * w >= W) {
// Cập nhật như bài toán unbounded knapsack (lấy không giới hạn)
// Duyệt từ trọng lượng w đến W (tăng dần) để không dùng một vật nhiều lần trong cùng một lần lặp
for (ll j = w; j <= W; j++) {
dp[j] = max(dp[j], dp[j - w] + v);
}
continue;
}
// Trường hợp bounded knapsack với k nhỏ: dùng sliding window
// Tạo bản sao dp cũ để tham chiếu (những giá trị trước khi thêm loại vật này)
vector<ll> dp_old = dp;
// Duyệt các phần dư r = 0..w-1
for(int r = 0; r < w; r++) {
// Sử dụng deque để lưu các cặp (t_index, H_value)
deque<pair<ll,ll>> dq;
// t là số đơn vị w đang xét, tương ứng vị trí j = r + t*w
ll max_t = (W - r) / w;
for(ll t = 0; t <= max_t; t++) {
ll j = r + t * w;
ll H = dp_old[j] - t * v; // giá trị H(t) = dp_old[r+t*w] - t*v
// Loại bỏ chỉ số đã ra khỏi phạm vi cửa sổ (t - k)
while (!dq.empty() && dq.front().first < t - k) {
dq.pop_front();
}
// Đưa chỉ số mới t vào deque, giữ thứ tự H giảm dần
while (!dq.empty() && dq.back().second <= H) {
dq.pop_back();
}
dq.emplace_back(t, H);
// Cập nhật dp[r + t*w] = dp_new[r+t*w]
// Công thức: t*v + max(H(u) trong cửa sổ) = deque.front().second + t*v
ll best = dq.front().second + t * v;
dp[j] = max(dp[j], best);
}
}
}
// Kết quả: giá trị lớn nhất trong dp[0..W]
ll ans = 0;
for(ll j = 0; j <= W; j++) {
ans = max(ans, dp[j]);
}
cout << ans;
return 0;
}
