#include <iostream>
#include <fstream>

using namespace std;

ifstream afile ("rucsac.in");
ofstream bfile ("rucsac.out");

int k[5001][10001];

int maxx (int a, int b)
{
	if (a>b) return a; else return b;
}

int main()
{
	int n,g;
	afile>>n>>g;
	int a[5001],b[5001];
	for (int i=1; i<=n; ++i)
		afile>>a[i]>>b[i];
	k[0][0]=0;
	for (int i=1; i<=n; i++)
	{
		k[0][i]=0;
		k[i][0]=k[i-1][0];
		if (a[i]==0) k[i][0]+=b[i];
	}
	for (int i=1; i<=n; i++)
		for (int j=1; j<=g; j++)
		{
			if (j<a[j]) k[i][j]=k[i-1][j];
			else k[i][j]=maxx(k[i-1][j-a[i]]+b[i],k[i-1][j]);
		}
	bfile<<k[n][g];
	return 0;
}