#include <fstream>

using namespace std;

int n , D[2][10002], P[5002] , W[5002]  , G;

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

static inline int max(int a,int b)
{
	return a > b ? a : b;
}

int main()
{
	fin>>n>>G;
	for(int i=1;i<=n;++i)
			fin>>W[i]>>P[i];
	int l = 0;
	for(int i=1;i<=n;++i,l = 1-l)
		for(int j=0;j<=G;++j)
			W[i]<=j ? D[1-l][j] = max(D[l][j],D[l][j-W[i]] + P[i]) : D[1-l][j] = D[l][j];

	fout<<D[l][G];
	return 0;
}