#include<fstream>
#define maxim(a,b)((a>b) ? a : b)
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int g[5001],cost[5001],mat[5001][10001];
int main()
{
	int i,j,k,l,n,gr,u,f,a;
	in>>n>>gr;
	for(i=1;i<=n;i++)
		in>>g[i]>>cost[i];
	a=1;
	for(i=1;i<=n;i++)
	{	for(j=1;j<=gr;j++)
		{
			if(g[i]<=j)
				mat[i][j]=maxim(mat[i-1][j],(mat[i-1][j-g[i]]+cost[i]));
			else
				mat[i][j]=mat[i-1][j];
		}
	}
	out<<mat[n][gr];	
	return 0;
}