#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(int arg_budget,int arg_diff){
		budget = arg_budget;
		diff = arg_diff;
	}
	int budget,diff;
};

int dp[101][10001],next_dp[101][10001];

int main(){

	int N,C,min_cost;
	scanf("%d %d",&N,&C);

	for(int i = 0; i <= C; i++){
		for(int k = 0; k <= 10000;k++){
			dp[i][k] = -1;
			next_dp[i][k] = -1;
		}
	}

	int high_score,low_score,next_high_score,next_low_score,next_diff;

	int add_A,add_B,cost;

	dp[C][0] = 0;

	vector<Info> Updated;

	min_cost = C;
	int next_min_cost;

	for(int loop = 0; loop < N; loop++){

		scanf("%d %d %d",&add_A,&add_B,&cost);

		next_min_cost = min_cost;

		for(int budget = C; budget >= max(min_cost,cost); budget--){

			for(int diff = 0; diff <= 10000; diff++){
				if(dp[budget][diff] == -1)continue;

				low_score = dp[budget][diff];
				high_score = low_score+diff;

				next_high_score = high_score+add_A;
				next_low_score = low_score+add_B;
				next_diff = next_high_score-next_low_score;
				if(next_dp[budget-cost][next_diff] < next_low_score){
					next_dp[budget-cost][next_diff] = next_low_score;
					Updated.push_back(Info(budget-cost,next_diff));
					next_min_cost = min(next_min_cost,budget-cost);
				}

				next_high_score = high_score+add_B;
				next_low_score = low_score+add_A;
				next_diff = max(next_high_score,next_low_score)-min(next_high_score,next_low_score);
				if(next_dp[budget-cost][next_diff] < min(next_high_score,next_low_score)){
					next_dp[budget-cost][next_diff] = min(next_high_score,next_low_score);
					Updated.push_back(Info(budget-cost,next_diff));
					next_min_cost = min(next_min_cost,budget-cost);
				}
			}
		}

		min_cost = next_min_cost;

		for(int i = 0; i < Updated.size(); i++){
			dp[Updated[i].budget][Updated[i].diff] = next_dp[Updated[i].budget][Updated[i].diff];
		}
		Updated.clear();
	}

	int ans = 0;

	for(int i = 0; i <= C; i++){
		for(int k = 0; k <= 10000; k++){
			ans = max(ans,dp[i][k]);
		}
	}

	printf("%d\n",ans);

	return 0;

}