#include<fstream>
using namespace std;
#define NMAX 5010
#define GMAX 10010

int n,gtotal;
int g[NMAX],c[NMAX];
int p[2][GMAX];

void read()
{
 int i;
 ifstream fin("rucsac.in");
 fin>>n>>gtotal;
 for (i=1; i<=n; ++i)
	 fin>>g[i]>>c[i];
 fin.close();
}

void solve()
{
 int i,j,lincurent,linprecedent;
 for (i=1; i<=n; ++i)
	{
	 lincurent = i % 2;
	 linprecedent = (3 - lincurent) % 2;
	 for (j=0; j<=gtotal; ++j)
		 if (g[i] <= j)
			 p[lincurent][j] = max(p[linprecedent][j], p[linprecedent][j-g[i]] + c[i]); else
			 p[lincurent][j] = p[linprecedent][j];
	}
}

void write()
{
 ofstream fout("rucsac.out");
 fout<<p[n%2][gtotal]<<'\n';
 fout.close();
}

int main()
{
 read();
 solve();
 write();
 return 0;
}