1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string>
 4 #include<string.h>
 5 #include<map>
 6 #include<math.h>
 7 #define Max(x,y) x>y?x:y
 8 using namespace std;
 9 
10 int dp[101][101][6];
11 int money[101],score[101],value[101];
12 int main()
13 {
14     int n,v1,v2,k;
15     while(cin>>n>>v1>>v2>>k)
16     {
17         memset(dp,0,sizeof(dp));
18         for(int i=0;i<n;i++)
19         {
20             cin>>money[i]>>score[i]>>value[i];
21         }
22         for(int i=0;i<n;i++)
23             for(int m=v1;m>=0;m--)
24                 for(int s=v2;s>=0;s--)
25                     for(int f=k;f>=0;f--)
26                     {
27                         int temp=0;
28                         if(f>0)
29                             temp=Max(temp,dp[m][s][f-1]+value[i]);
30                         if(s>=score[i])
31                             temp=Max(temp,dp[m][s-score[i]][f]+value[i]);
32                         if(m>=money[i])
33                             temp=Max(temp,dp[m-money[i]][s][f]+value[i]);
34                         dp[m][s][f]=Max(temp,dp[m][s][f]);
35                     }
36     printf("%d\n",dp[v1][v2][k]);
37     }
38 
39     return 0 ;
40 }