#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("rucsac.in");
ofstream out ("rucsac.out");

int n,g;
int **dp, *p, *w;

inline int max(int a, int b)
{
	if(a>b)return a;
	return b;
}
void init();
void destroy();
int main()
{
	in >> n >> g;
	init();
	for(int i = 1; i <= n; i++)
		in >> w[i] >> p[i];
	for(int i = 1; i <= n; i++)
	{
		for(int j = 0; j <= g; j++)
		{
			cerr << i << ' ' << j << '\n';
			if(j >=w[i])
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
			else
				dp[i][j]=dp[i-1][j];
		}
	}
	out << dp[n][g];
	destroy();
}

void init()
{
	dp = new int*[n+1];
	for(int i = 0; i <= n; i++)
		dp[i]=new int[g+1];
	p = new int[n+2];
	w = new int[n+2];
	for(int i = 0; i <= g; i++)
		dp[0][i]=0;
}
void destroy()
{
	for(int i = 0; i <= n; i++)
		delete[] dp[i];
	delete[] dp;
	delete[] p;
	delete[] w;
}