#include<iostream>
#include<fstream>
using namespace std;

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

int P[5000],W[5000],Best[10000],N,G,i,j;

int main(){
	
in>>N>>G;

for(i=1;i<=N;i++)
	in>>W[i]>>P[i];

for(i=1;i<=N;i++)
	for(j=G-W[i];j>=0;j--)	
		if(Best[j+W[i]]<Best[j]+P[i])	Best[j+W[i]]=Best[j]+P[i];
	
out<<Best[G];
		
return 0;
}