#include <fstream>
using namespace std;
#define dim 100000
int c[dim], g[dim], f[dim], val[dim];
int main()
{
	ifstream fin("rucsac.in");
	ofstream fout("rucsac.out");
	int n, G, i;
	fin>>n >>G;
	
	for(i=1;i<=n;++i)
		fin>>g[i] >>c[i];
		
	f[0]=1;
	
	int max=0;
	for(i=1;i<=n;++i)
		for(int j=max;j>=0;--j)
			if(f[j]==1 && j+g[i]<=G)
			{
				f[j+g[i]]=1;
				
				if(val[j]+c[i]>val[j+g[i]])
					val[j+g[i]]=val[j]+c[i];
				
				if(j+g[i]>max)
					max=j+g[i];
				
			}
	
			fout<<val[G];
			
	return 0;
}