#include<fstream>
using namespace std;
int d[2][10001],w[5001],p[5001],n,gr;


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

int main()
{
	

	
ifstream f("rucsac.in");
ofstream g("rucsac.out");
	
	
	f>>n>>gr;
	
	for(int i=1;i<=n;i++)
		f>>w[i]>>p[i];

	int l=0;
	for(int i=1;i<=n;i++,l=1-l)
		for(int j=0;j<=gr;j++)
		{
			d[1-l][j]=d[l][j];
			if(w[i]<=j)
			d[1-l][j] = maximus(d[1-l][j], d[l][j - w[i]] + p[i]); 
       }
g<<d[l][gr];
}