1 /*
 2 Author:    Leo.W
 3 Descriptipn:    0-1背包問題，預算資金m元，n件物品，給出他們的價格、最低買入擁有金、估價。        
 4 How to Do:    dp[j]=max{dp[j],dp[j-c[i]]+w[i]}
 5   */
 6 #include <iostream>
 7 #include <string.h>
 8 #include <algorithm>
 9 using namespace std;
10 #define max(a,b) (a)>(b)?(a):(b)
11 struct shell{
12     int c;
13     int p;
14     int w;
15 }sh[501];
16 int dp[5005];
17 int cmp(shell a,shell b){//此處排序設計是關鍵，要保證放入貴的物品時，廉價貨已經放入。
18 //最初只考慮是a.p-b.p,后來覺得實質上在DP時a.c與b.c都被剪掉了，且默認p>c的
19     return a.p-a.c<b.p-b.c;
20 }
21 int main(){
22     //freopen("in.txt","r",stdin);
23     int n,m;
24     while (scanf("%d%d",&n,&m)!=EOF){
25         int i,j;
26         for(i=0;i<n;i++)    scanf("%d%d%d",&sh[i].c,&sh[i].p,&sh[i].w);
27         sort(sh,sh+n,cmp);//排序是解此題的關鍵
28         memset(dp,0,sizeof(dp));
29         for(i=0;i<n;i++){
30             for(j=m;j>=sh[i].p;j--)
31                 dp[j]=max(dp[j],dp[j-sh[i].c]+sh[i].w);
32         }
33         printf("%d\n",dp[m]);
34     }
35     return 0;
36 }
37