1 #include<iostream>
2 #include<queue>
3 using namespace std;
4 struct node
5 {
6 int h,c,a;
7 }a[410];
8 int dp[40010];
9 bool cmp(const node & n1,const node & n2)
10 {
11 return n1.a<n2.a;
12 }
13
14 int main()
15 {
16 int k;
17 int maxHeight=0;
18 cin>>k;
19 for(int i=1;i<=k;i++)
20 {
21 cin>>a[i].h>>a[i].a>>a[i].c;
22 maxHeight=max(maxHeight,a[i].a);
23 }
24 sort(a+1,a+1+k,cmp);
25 memset(dp,0,sizeof(dp));
26 dp[0]=1;
27 for(int i=1;i<=k;i++)
28 {
29 for(int j=a[i].a-a[i].h;j>=0;j--)
30 {
31 if(dp[j])
32 {
33 for(int t=1;t<=a[i].c;t++)
34 {
35 if(j+t*a[i].h>a[i].a) break;
36 dp[j+t*a[i].h]=1;
37 }
38 }
39 }
40 }
41 while(maxHeight)
42 {
43 if(dp[maxHeight]) break;
44 maxHeight--;
45 }
46 cout<<maxHeight<<endl;
47 }