/* #include using namespace std; int main(){ */ // __builtin_popcount() ; // multiset ; // unordered_set ; // unordered_map ; // reverse ; /* #include using namespace atcoder ; // using mint = modint; // using mint = modint998244353 ; // using mint = modint1000000007 ; */ #include using namespace std; /* #include using namespace boost::multiprecision; typedef cpp_int cp ; */ //-------型------- typedef long long ll; typedef string st ; typedef long double ld ; typedef unsigned long long ull ; using P = pair ; using run = pair ; using Edge = tuple ; using AAA = tuple ; //-------型------- //-------定数------- const ll mod0 = 1000000007; const ll mod1 = 998244353 ; const ll LINF = 1000000000000000000+2 ; //(10^18) const ld pai = acos(-1) ; const ld EPS = 1e-10 ; //-------定数------- //-------マクロ------- #define pb push_back #define ppb pop_back #define pf push_front #define ppf pop_front #define all(x) x.begin(), x.end() #define rep(i,a,n) for (ll i = a; i <= (n); ++i) #define rrep(i,a,b,c) for (ll i = a ; i <= (b) ; i += c) #define ketu(i,a,n) for (ll i = a; i >= (n); --i) #define re return 0; #define fore(i,a) for(auto &i:a) #define V vector #define fi first #define se second #define C cout #define E "\n"; #define EE endl; //-------マクロ------- //-------テンプレ文字列------- st zz = "abcdefghijklmnopqrstuvwxyz" ; st ZZ = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ; st tintin = "%" ; st Y = "Yes" ; st YY = "No" ; st KU = " " ; //-------テンプレ文字列------- void chmin(ll& x ,ll y){x = min(x,y) ;} void chmax(ll& x ,ll y){x = max(x,y) ;} ll max_element(V &A){ ll res = *max_element(all(A)) ; return res ; } ll max_element_index(V &A){ ll res = max_element(all(A)) - A.begin() ; return res ; } ll min_element(V &A){ ll res = *min_element(all(A)) ; return res ; } ll min_element_index(V &A){ ll res = min_element(all(A)) - A.begin() ; return res ; } vector Y4 = {0,1,0,-1} ; vector X4 = {1,0,-1,0} ; vector Y8 = {0,1,1,1,0,-1,-1,-1} ; vector X8 = {1,1,0,-1,-1,-1,0,1} ; ll gcd(ll a, ll b){ if(b == 0){ return a; } return gcd(b,a%b) ; } ll lcm(ll a, ll b){ ll ans = a*b /gcd(a,b) ; return ans ; } template T pow_mod(T A, T N, T M) { T res = 1 % M; A %= M; while (N) { if (N & 1) res = (res * A) % M; A = (A * A) % M; N >>= 1; } return res; } // Miller-Rabin 素数判定 bool nis(ll N) { if (N <= 1) return false; if (N == 2) return true; if (N == 3) return true ; if (N == 5) return true ; if (N == 7) return true ; if (N == 11) return true ; if (N % 2 == 0 || N % 3 == 0 || N % 5 == 0 || N % 7 == 0 || N % 11 == 0 ) return false ; vector A = {2, 325, 9375, 28178, 450775,9780504, 1795265022}; ll s = 0, d = N - 1; while (d % 2 == 0) { ++s; d >>= 1; } fore(a,A) { if (a % N == 0) return true; ll t, x = pow_mod<__int128_t>(a, d, N); if (x != 1) { for (t = 0; t < s; ++t) { if (x == N - 1) break; x = __int128_t(x) * x % N; } if (t == s) return false; } } return true; } // UF.initはいっかいだけならいいけど、二回目以降はrepで初期化 vector par; class UnionFind { public: // サイズをGET! void init(ll sz) { par.resize(sz,-1); } // 各連結成分の一番上を返す ll root(ll x) { if (par[x] < 0) return x; return par[x] = root(par[x]); } // 結合作業 bool unite(ll x, ll y) { x = root(x); y = root(y); if (x == y) return false; if (par[x] > par[y]) swap(x,y); par[x] += par[y]; par[y] = x; return true; } // 同じグループか判定 bool same(ll x, ll y) { return root(x) == root(y);} // グループのサイズをGET! ll size(ll x) { return -par[root(x)];} }; UnionFind UF ; vector enumdiv(ll n) { vector S; for (ll i = 1; i*i <= n; i++) if (n%i == 0) { S.pb(i); if (i*i != n) S.pb(n / i); } sort(S.begin(), S.end()); return S; } template using min_priority_queue = priority_queue, greater>; template using max_priority_queue = priority_queue, less> ; // 使用例 min_priority_queue Q ; vector> prime_factorize(long long N){ vector> res; for(long long a = 2; a * a <= N; ++a){ if(N % a != 0) continue; long long ex = 0; while(N % a == 0) ++ex, N /= a; res.push_back({a,ex}); } if(N != 1) res.push_back({N,1}); return res; } ll binpower(ll a, ll b,ll c) { if(!b) return 1 ; a %= c ; ll d = binpower(a,b/2,c) ; (d *= d) %= c ; if(b%2) (d *= a) %= c ; return d ; } template V sr(V A){ sort(all(A)) ; reverse(all(A)) ; return A ; } map Compression(V A){ sort(all(A)) ; A.erase(unique(all(A)),A.end()) ; map res ; ll index = 0 ; fore(u,A){ res[u] = index ; index ++ ; } return res ; } V sort_erase_unique(V &A){ sort(all(A)) ; A.erase(unique(all(A)),A.end()) ; return A ; } struct sqrt_machine{ V A ; const ll M = 1000000 ; void init(){ A.pb(-1) ; rep(i,1,M){ A.pb(i*i) ; } A.pb(LINF) ; } bool scan(ll a){ ll pos = lower_bound(all(A),a) - A.begin() ; if(A[pos] == -1 || A[pos] == LINF || A[pos] != a)return false ; return true ; } }; sqrt_machine SM ; ll a_b(V A,ll a,ll b){ ll res = 0 ; res += upper_bound(all(A),b) - lower_bound(all(A),a) ; return res ; } struct era{ ll check[10000010] ; void init(){ rep(i,2,10000000){ if(check[i] == 0){ for(ll j = i + i ;j <= 10000000 ; j += i){ check[j] ++ ; } } } } bool look(ll x){ if(x == 1)return false ; if(check[x] == 0)return true ; else return false ; } ll enu_count(ll x){ if(x == 1)return 1 ; if(check[x] == 0)return 1 ; return check[x] ; } }; era era ; st ten_to_two(ll x){ st abc = "" ; if(x == 0){ return "0" ; } while(x > 0){ abc = char(x%2 + '0') + abc ; x /= 2 ; } return abc ; } ll two_to_ten(st op){ ll abc = 0 ; ll K = op.size() ; for(ll i = 0 ;i < K ;i++){ abc = abc * 2 + ll(op[i] - '0') ; } return abc ; } ll powpow(ll A , ll B){ ll res = 1 ; rep(i,1,B){ res *= A ; } return res ; } V Run_Length_Encoding(st S){ ll N = S.size() ; V> A ; ll count = 0 ; char cc ; bool RLEflag = false ; if(N == 1){ A.pb({S[0],1}) ; RLEflag = true ; } rep(i,0,N-1){ if(RLEflag == true)break ; if(i == 0){ cc = S[i] ; count = 1 ; continue ; } if(i == N-1){ if(S[i] == cc){ A.pb({cc,count + 1}) ; }else{ A.pb({cc,count}) ; A.pb({S[i],1}) ; } break ; } if(S[i] == cc){ count ++ ; }else{ A.pb({cc,count}) ; cc = S[i] ; count = 1 ; } } return A ; } struct Two_Dimensional_Vector{ void pr(V> A){ ll N = A.size() ; ll M = A[0].size() ; rep(i,0,N-1){ rep(j,0,M-1){ C << A[i][j] << KU ; } C << E } } V> iv(ll N , ll M){ V> A(N,V(M)) ; rep(i,0,N-1){ rep(j,0,M-1){ cin >> A[i][j] ; } } return A ; } ll Matrix_count(V> A,ll x){ ll N = A.size() ; ll M = A[0].size() ; ll count = 0 ; rep(i,0,N-1){ rep(j,0,M-1){ if(A[i][j] == x)count ++ ; } } return count ; } } ; Two_Dimensional_Vector tdv ; ll kiriage(ll a , ll b){ return (a + b - 1) / b ; } ll a_up(V &A , ll x){ if(A[A.size()-1] < x)return -1 ; ll res = lower_bound(all(A),x) - A.begin() ; return A[res] ; } ll b_down(V &B , ll x){ if(B[0] > x)return -1 ; ll res = upper_bound(all(B),x) - B.begin() ; return B[res-1] ; } ll Permutation(ll N){ ll res = 1 ; rep(i,1,N)res *= i ; return res ; } V> Next_permutation(ll N){ ll Size = Permutation(N) ; V> res(Size) ; V per(N) ; rep(i,0,N-1)per[i] = i ; ll count = 0 ; do{ fore(u,per){ res[count].pb(u) ; } count ++ ; }while(next_permutation(per.begin(),per.end())); return res ; } /* st Regex(st S, st A ,st B){ return regex_replace(S,regex(A),B) ; } st erase_string(st S , st T){ st ans = S.erase(S.find(T),T.length()) ; return ans ; } */ int main(void){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); // SM.init() ; // era.init() ; // max_element(V A) Aの最大値を返す // max_element_index(V A) Aの最大値のindex // min_element(V A) Aの最小値を返す // min_element_index(V A) Aの最小値のindex // gcd(ll a , ll b) gcd // lcm(ll a ,ll b ) lcm // nis(ll a) 素数判定 素数ならtrue // UF UF.init(ll N) ; UF.root(i) ; UF.unite(a,b) ; UF.same(a,b) ; UF.size(i) ; // enumdiv(ll a )約数列挙 // prime_factorize(ll p) aのb乗のかたちででてくる 配列で受け取る // binpower(a,b,c) aのb条 をcでわったやつをO(logb) ぐらいでだしてくれるやつ // sr(V A) 配列を入れたら、sort --→ reverse して返してくれる関数 受け取りは auto とかで // sort_erase_unique(V A) sortしてeraseしてuniqueする関数 // Compression(V A) 座圧したmapを返す関数 // SM.scan(ll a) で 平方数ならtrue が返ってくる。 範囲は √10^6まで SM.init() 必ず起動する。 // a_b(A,a,b) [a,b]の個数 ---→ upper_bound(all(A),b) - lower_bound(all(A),a) ; // era.look(ll a) --→ true 素数 / era.enu_count(ll a) --→ 素因数の個数 1は1 、素数も1 その他はそのまんま 範囲は10^7まで // ten_to_two(ll x) 10進数を二進数にして返す。文字列で出力する事に注意 ll --→ st // two_to_ten(st a) 2進数を10進数にして返す。 st --→ ll // powpow(ll a,ll b) a^b を返す // Run_Length_Encoding(st S) ランレングス圧縮して配列を返す pair // Regex(st S, st A , st B) SのAをBに変えた文字列を返す 使う場合は消す // erase_string(st S , st T) Sの中のTを消す // Two_Dimensional_Vector tdv.pr(V> A) Aを出力 tdv.iv(N,M) 配列を受け取る main内で auto A = tdv.iv(N,M) ;とする Matrix_count(V> , x)Aのなかのxの個数を返す // kiriage(ll a , ll b) a 割られる数 b 割る数 // a_up(V A , ll x) sort済み配列でx以上の最小値を返す。ない場合、-1を返す. // b_down(V B , ll x)sort済み配列でx以下で最大値を返す。ない場合 -1を返す。 // Permutation(ll N) N!の値を返す。20までならオーバーフローしない。 // V> Next_permutation(ll N) next_permutationした配列の集合を返す. // (double)clock()/CLOCKS_PER_SEC>1.987 // multisetで1つだけ要素消したかったら、 A.erase(A.find(x)) ;とする。 // mod0 --→ 1000000007 mod1 --→ 998244353 // 座圧した後、size変わることに注意。二回やらかしてます ll N,x,y ; cin >> N >> x >> y ; V cute(N) ; rep(i,0,N-1){ ll a,b,c ; cin >> a >> b >> c ; cute[i] = {a,b,c} ; } V>> dp(N+1,V>(x+1,V(y+1,-LINF))) ; dp[0][0][0] = 0 ; rep(i,0,N-1){ rep(j,0,x){ rep(k,0,y){ if(dp[i][j][k] == -LINF) continue ; auto [a,b,c] = cute[i] ; chmax(dp[i+1][j][k],dp[i][j][k]) ; if(j + a <= x && k + b <= y)chmax(dp[i+1][j+a][k+b],dp[i][j][k] + c) ; } } } ll ans = 0 ; rep(i,0,N){ rep(j,0,x){ rep(k,0,y){ chmax(ans,dp[i][j][k]) ; } } } C << ans << E // if(dx < 0 || dy < 0 || dx >= W || dy >= H) continue ; // C << fixed << setprecision(10) << // 勝手に四捨五入してくれてるから安心して re }