@zhang

#include<bits/stdc++.h>
using namespace std;
int dp[2][501][1002];//前i个菜，花了v元，小明心情为k时小红心情的最大值
int main() {
	int n,v;
	cin>>n>>v;
	memset(dp,0Xf0,sizeof dp);
	dp[0][0][500]=0;
	for(int i=1; i<=n; i++) {
		int c,x,y;
		cin>>c>>x>>y;
		for(int j=0; j<=v; j++) {
			for(int k=0; k<=1000; k++) {
				if(k-x>=0&&k-x<=1000&&j-c>=0) {
					dp[i%2][j][k]=max(dp[(i-1)%2][j][k],dp[(i-1)%2][j-c][k-x]+y);
				} else {
					dp[i%2][j][k]=dp[(i-1)%2][j][k];
				}

			}
		}
	}
	int ans=0;
	for(int j=1; j<=v; j++) {
		for(int i=500; i<=1000; i++) {
			ans=max(ans,dp[n%2][j][i]);
		}
	}
	cout<<ans;
}