#include <fstream>
using namespace std;
int main()
{
	int n, maxg, greu[5005], pret[5005], din[2][10005], i, j;
	ifstream f("rucsac.in");
	ofstream g("rucsac.out");
	f>>n>>maxg;
	for(i=1; i<=n; i++)
	{
		f>>greu[i]>>pret[i];
	}
	int l=0;
	for(i=1; i<=n; l=1-l, i++)
	{
		for(j=0; j<=maxg; j++)
		{
			din[1-l][j]=din[l][j];
			if(greu[i]<=j)
			din[1-l][j]=max(din[1-l][j], din[l][j-greu[i]]+pret[i]);
		}
	}
	g<<din[l][maxg];
}