#include <iostream>
#include <fstream>

using namespace std;

fstream in("rucsac.in", ios::in);
fstream out("rucsac.out", ios::out);

#define nmax 5001

int n,g,pret[nmax],greu[nmax],tabla[nmax][nmax];
int maxim(int,int);

int main()
{
	int i,j,k;

	in>>n>>g;

	for(i=1;i<=n;i++)
	{
		in>> greu[i];
		in>> pret[i];
	}

	for(i=1;i<=n;i++)
		for(j=1;j<= g;j++)
		{
			if(j == greu[i])
				tabla[i][j]= max(pret[i],tabla[i-1][j]);
			else
				tabla[i][j]= max(tabla[i][j-1],tabla[i-1][j]);
			if(j - greu[i] >= 0)
				if( pret[i]+ tabla[i-1][j-greu[i]] > tabla[i-1][j-greu[i]])
					tabla[i][j]=  max(pret[i]+ tabla[i-1][j-greu[i]],tabla[i-1][j]);
		}

		/*
	for(i=1;i<=n;i++)
	{
		for(j=1;j<= g;j++)
			cout<< tabla[i][j]<< " ";
		cout<< "\n";
	}

	*/
    out<<tabla[n][g];
    in.close();
    out.close();

	return 0;
}

int maxim(int a,int b)
{
	return (a >= b)?  a : b;
}