#include <bits/stdc++.h>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int ct;
int i,n,g, a[5000][5000];
int c[5000],go[5000];
void cit()
{
	fi>>n>>g;
	for(i=1;i<=n;i++)
	{
	fi>>go[i]>>c[i];	
	}
}

void scri()
{
    fo<<a[ct][g]; 

}
void ex()
{
	int u,z=1;
	for(int i=1;i<=n ;i++)
	{
	u=z;	
	z=1-z;
	for(int j=1;j<=g ;j++)
	{
	if (go[i]>j) a[u][j]=a[z][j];
		else 
	a[u][j]=max(a[z][j],a[z][j-go[i]]+c[i])	;
		}	
		ct=u;	
	}
}
int main()
{
	cit();
	ex();
	scri();
	return 0;
}