#include <fstream> 
using namespace std; 
ifstream fin ("rucsac.in"); 
ofstream fout ("rucsac.out");   
int n,g,v[5001],w[5001],t[10001],i,j;
int main() {     
	fin>>n>>g;     
	for (i=1;i<=n;i++) 
		fin>>w[i]>>v[i];     
	for (i=1;i<=n;i++)
	{         
		for (j=g;j>=w[i];j--)         
			if (t[j-w[i]]+v[i]>t[j]) 
				t[j]=t[j-w[i]]+v[i];     
	}     
	fout<<s[g]; 
return 0;
}