#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int N, X;
	cin >> N >> X;
	vector<int> value, day;
	int day_t, value_t;
	while (cin >> value_t >> day_t)
	{
		day.push_back(day_t);
		value.push_back(value_t);
	}
	vector<vector<int>> dp(N + 1, vector<int>(X + 1, 0));
	int res = 0;
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= X; ++j)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= day[i - 1])
			{
				dp[i][j] = max(dp[i][j], dp[i - 1][j - day[i - 1]] + value[i - 1]);
			}
			res = max(res, dp[i][j]);


		}
	}
	cout << res << endl;
}

#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;

void DFS(unordered_map<int, vector<pair<int, int>>>& mps, unordered_map<int, bool>& visit, int a, int& res, int end, int sum)
{
	if (a == end)
	{
		res = min(res, sum);
		return;
	}
	for (auto mp : mps[a])
	{
		if (visit[mp.first]) continue;
		sum += mp.second;
		visit[mp.first] = true;
		DFS(mps, visit, mp.first, res, end, sum);
		visit[mp.first] = false;
		sum -= mp.second;
	}
	return;
}

int main()
{
	int N, P;
	cin >> N >> P;
	unordered_map<int, vector<pair<int, int>>> mps;
	unordered_map<int, bool> visit;
	for (int i = 0; i < P; ++i)
	{
		int A, B, T;
		cin >> A >> B >> T;
		mps[A].push_back(make_pair(B, T));
		visit[A] = false;
		visit[B] = false;
	}
	int end;
	cin >> end;
	int res = 10000;
	DFS(mps, visit, 0, res, end, 0);
	cout << res << endl;
	return 0;
}




#include<iostream>
#include<vector>

using namespace std;

int main()
{
	int N, X;
	cin >> N >> X;
	vector<int> value, day;
	int day_t, value_t;
	while (cin >> value_t >> day_t)
	{
		day.push_back(day_t);
		value.push_back(value_t);
	}
	vector<vector<int>> dp(N + 1, vector<int>(X + 1, 0));
	int res = 0;
	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= X; ++j)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= day[i - 1])
			{
				dp[i][j] = max(dp[i][j], dp[i - 1][j - day[i - 1]] + value[i - 1]);
			}
			res = max(res, dp[i][j]);


		}
	}
	cout << res << endl;
}