#include <iostream>
#include <fstream>

using namespace std;

int max(int x, int y)
{
	if(x > y) 
	{
		return x;
	}
	else 
	{
		return y;
	}
}

int main()
{
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	int n,G,g[5002],p[5002],a[100000];
	fin >> n >> G;
	for(int i = 1; i <= n; i++)
	{
		fin >> g[i] >> p[i];
	}
	for(int i = 0; i <= G; i++)
	{
		a[i] = 0;	
	}	
	for(int i = 1; i <= n; i++)
	for(int j = G; j >= 0; j--)
	{
		if( j - g[i] >= 0)
		{
			a[j] = max(a[j], a[j-g[i]]+p[i]);
		}
	}
	fout << a[G];	
	return 0;
}