#include <fstream>
#include <string.h>
using namespace std;

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

int profit[10005],W[5005],P[5005];
int N,G;

int main() {
	fin >> N >> G;
	for(int i=1;i<=N;++i) fin >> W[i] >> P[i];
	for(int i=1;i<=N;++i)
		profit[i]=-1;
	for(int i=1;i<=N;++i)
		for(int j=G-W[i];j>=0;--j)
			profit[j+W[i]]=max(profit[j+W[i]],profit[j]+P[i]);
	fout << profit[G];
	return 0;
}