#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N, G;

struct item
{
	int weight;
	int price;
};

item items[5001];
int solve()
{
	vector<vector<int>> matrix(2, vector<int>(G + 1));
	for (int i = 1; i <= N; i++)
	{
		for (int curr_weight = 0; curr_weight <= G; curr_weight++)
		{
			matrix[1][curr_weight] = matrix[0][curr_weight];
			
			if (curr_weight - items[i].weight >= 0)
			{
				matrix[1][curr_weight] = max(matrix[1][curr_weight], matrix[0][curr_weight - items[i].weight] + items[i].price);
			}
		}
		matrix[0] = matrix[1];
	}
	return matrix[1][G]; 
}

int main()
{
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	// Program
	
	f >> N;
	f >> G;
	for (int i = 1; i <= N; i++)
	{
		item temp;
		f >> temp.weight;
		f >> temp.price;
		items[i] = temp;
	}
	g << solve();

	// Exit
	f.close();
	g.close();
	return 0;
}