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

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

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