#include<iostream>
#include<fstream>

using namespace std;

int main()
{ifstream f("rucsac.in",ios::in);
ofstream g("rucsac.out",ios::out);

int N,G;
int V[10010],W[5010],P[5010];
int i,j;

f>>N>>G;
for(i=1;i<=N;i++)
	f>>W[i]>>P[i];
for(i=0;i<=G;i++)
	V[i]=0;

for(i=1;i<=N;i++)
	{
	for(j=G;j>=0;j--)
	{
		if(W[i]<=j && V[j]<V[j-W[i]]+P[i])
			V[j]=V[j-W[i]]+P[i];}}
int m=0;
for(i=0;i<=G;i++)
	if(m<V[i])
		m=V[i];
g<<m<<endl;
f.close();
g.close();
return 0;
}