#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); //店iでX回交換するのに必要な缶の数 //(A-B)個補充すれば1回交換できる。(初めはA個) //A+(X-1)(A-B)個 //dp(i, j)=i番目の店まででj個以下の缶で得られる嬉しさの最大値 ll N, M, A, B, C; const ll inf = -1e18; cin >> N >> M; vector dp(N+1, vector<ll>(M+1, inf)); dp[0][0] = 0; for (int i=1; i<=N; i++){ cin >> A >> B >> C; //まずは1個買う for (int j=0; j<=M; j++){ if (j-A>=0 && dp[i-1][j-A] != inf) dp[i][j] = max(dp[i][j], dp[i-1][j-A]+B*C); } //その後補充 for (int j=0; j<=M; j++){ if (j-(A-B)>=0 && dp[i][j-(A-B)] != inf) dp[i][j] = max(dp[i][j], dp[i][j-(A-B)]+B*C); } //i番目の店で1個も交換しない for (int j=0; j<=M; j++) dp[i][j] = max(dp[i][j], dp[i-1][j]); } ll mx = 0; for (int i=1; i<=M; i++){ mx = max(mx, dp[N][i]); cout << mx << endl; } return 0; }