import std; void main () { // input int N, X, Y; { auto buf = readln.split.to!(int[]); N = buf[0], X = buf[1], Y = buf[2]; } int[] A, B, C; foreach (_; 0..N) { auto buf = readln.split.to!(int[]); A ~= buf[0], B ~= buf[1], C ~= buf[2]; } solve(N, X, Y, A, B, C); } void solve (int N, int X, int Y, int[] A, int[] B, int[] C) { int[][] dp = new int[][](X+1, Y+1); // dp[i][j] := 「メニュー枠i, 容量jを消費して達成できる最大かわいさ」 // dp[i+A_k][j+B_k] = max(dp[i][j] + C_k, dp[i+A_k][j+B_k]) if dp[i][j] != -1 && i+A_k <= X && j+B_k <= Y // initialize foreach (ref x; dp) { x[] = -1; } dp[0][0] = 0; // DP // 基本的なアイデアは一次元DPの「組み合わせ全列挙の圧縮」にほかならない foreach (k; 0..N) { foreach_reverse (i; 0..X+1) { foreach_reverse (j; 0..Y+1) { if (dp[i][j] != -1 && i + A[k] <= X && j + B[k] <= Y) { dp[i+A[k]][j+B[k]] = max(dp[i][j] + C[k], dp[i+A[k]][j+B[k]]); } } } } // output int ans = 0; foreach (i; 0..X+1) { foreach (j; 0..Y+1) { if (dp[i][j] != -1) { ans = max(ans, dp[i][j]); } } } writeln(ans); }