#include using namespace std; typedef long long ll; typedef long double ld; typedef pair PP; // #define MOD 1000000007 #define MOD 998244353 #define INF 2305843009213693951 //#define INF 810114514 #define PI 3.141592653589 #define setdouble setprecision #define REP(i,n) for(ll i=0;i<(n);++i) #define OREP(i,n) for(ll i=1;i<=(n);++i) #define RREP(i,n) for(ll i=(n)-1;i>=0;--i) #define ORREP(i,n) for(ll i=(n);i>=1;--i) #define rep(i,a,b) for(ll i=(a);i<=(b);++i) #define ALL(v) (v).begin(), (v).end() #define GOODBYE do { cout << "-1" << endl; return 0; } while (false) #define MM <<" "<< #define Endl endl #define debug true #define debug2 false int main(void){ //cin.tie(nullptr); //ios::sync_with_stdio(false); ll N,W,D; cin >> N >> W >> D; vector W1,W2,V1,V2; REP(i,N){ ll t,w,v; cin >> t >> w >> v; if(t==0){ W1.push_back(w); V1.push_back(v); }else{ W2.push_back(w); V2.push_back(v); } } // dp[i][j] := iまで見た、重量がj以下のときの最大価値 vector dp1(W+1,-INF),dp2(W+1,0); dp1[0]=0; REP(i,W1.size()){ vector tmp(W+1,-INF); REP(j,W+1){ // 選ばない tmp[j] = max(tmp[j],dp1[j]); // 選ぶ if(j+W1[i]<=W){ tmp[j+W1[i]] = max(tmp[j+W1[i]],dp1[j]+V1[i]); } } swap(dp1,tmp); } REP(i,W2.size()){ vector tmp(W+1,0); REP(j,W+1){ // 選ばない tmp[j] = max(tmp[j],dp2[j]); // 選ぶ if(j+W2[i]<=W){ tmp[j+W2[i]] = max(tmp[j+W2[i]],dp2[j]+V2[i]); } } swap(dp2,tmp); } // REP(i,W+1){cout << dp1[i] << " ";}cout << endl; // REP(i,W+1){cout << dp2[i] << " ";}cout << endl; ll Ans = 0; REP(i,W+1){ ll k = min(W-i,i+D); if(abs(i-k)<=D){ Ans = max(Ans,dp1[i]+dp2[k]); } } cout << Ans << endl; return 0; }