Proud Merchants

//题意：
//小明去古董城买古董，但古董城有个规矩，如果你手里的钱少于商家给的出手价Q，即使你的钱可以
//买下这个古董，但商家也不会卖给你，因为你没有出手的资本。
//小明是个古董行家，他能评估出古董的真正价值 
//现在有n件古董，小明有m元， 
//每件古董价格为 P ，出售价为 Q ，古董的真正价格为 V 。
//计算小名可以获得的最大的商品的真正价值是多少 

//解题思路：：
//大神写的，，很详细 
//首先可以肯定的是，这是一个01背包问题，但要对其进行一定的处理
// 比如A:p1 q1, B:p2 q2，然后，假设单独买A或者B的话，都是可以买到的。这时，若先买A，
//则你至少需要p1+q2的钱；若先买B，则至少需要p2+q1的钱。那肯定是花最少的钱咯，所以如
//果先买A再买B，那么p1+q2<p2+q1，转换一下，就是q1-p1>q2-p2，也就是说qi-pi大的先买。
//这里还得注意一点就是，排序的时候，得按照qi-pi从小到大排序，因为你买第n件商品的时候，
//是在比较你是否要先买第n件商品。打个比方让大家更好地理解，比如说f(3, 10)，是不是
//max(f(2, 10-p3)+v3, f(2, 10))，你会发现这个第一种情况f(2,10-p3)+v3中，是先买了第三件商品，
//也就是说排在后面的商品会先买。好的，排好序之后，就把问题就转换为不需要考虑顺序的问题了，
//那就是上面我们已经解决0/1背包问题了。这样，问题圆满解决了。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int sum[10100];
struct zz
{
	int p,q,v;
}a[100010];
int cmp(zz a,zz b)
{
	return a.q-a.p<b.q-b.p;
}
int main(){
	int n,m,i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(sum,0,sizeof(sum));
		for(i=0;i<n;i++)
			scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
		sort(a,a+n,cmp);
		for(i=0;i<n;i++)
		{
			for(j=m;j>=a[i].p&&j>=a[i].q;j--)
			{
				sum[j]=max(sum[j],sum[j-a[i].p]+a[i].v);
			}
		}
		printf("%d\n",sum[m]);
	}
	return 0;
}