#include<cstring>
#include<fstream>
#include<vector>
#include<algorithm>
#define maxn 5001
#define maxg 10001

using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int w[maxn], p[maxn],n,g,sol;
int Optim[maxg];

int main()
{
	fin>>n>>g;
	for (int i = 1; i <= n; ++i)
		fin>>w[i]>>p[i];

	for( int i = 1; i <= n; ++i)
		for( int j = g - w[i]; j >= 0; --j)
			if( Optim[j+w[i]] < Optim[j] + p[i] )
			{
				Optim[j+w[i]] = Optim[j] + p[i];
				if( Optim[j+w[i]] > sol)
					sol = Optim[j+w[i]];
			}
	fout<<sol;
	return 0;
}