#include <bits/stdc++.h>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int ct,i,n,g, a[5000][5000], c[5000],go[5000];
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()
{
    	fi>>n>>g;
	for(i=1;i<=n;i++)	fi>>go[i]>>c[i];	
	ex();
fo<<a[ct][g]; 
	return 0;
}