#include <iostream>
#include <fstream>

#define WMAX 5010
#define GMAX 1010

using namespace std;

int uz[WMAX][GMAX];
int CMax[WMAX];
int C[GMAX];
int W[GMAX];
int N,Wtot;

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

int main() {
	int i,j,k;

	memset(uz,0,sizeof(uz));
	memset(CMax,-1,sizeof(CMax));
	
	CMax[0] = 0;
	
	fin >> N;
	fin >> Wtot;
	for (i=0;i<N;++i) {
		fin >> W[i] >> C[i];
	}
	
	for (i=0;i<=Wtot;++i) {
		for (j=0;j<N;++j) {
			if ((W[j] <= i) && (CMax[i-W[j]] != -1) && (!uz[i-W[j]][j])) {
				if (CMax[i] < CMax[i-W[j]] + C[j]) {
					CMax[i] = CMax[i-W[j]] + C[j];
					for (k=0;k<N;++k)
						uz[i][k] = uz[i-W[j]][k];
					uz[i][j] = 1;
				}
			}
		}		
	}
	
	fout << CMax[Wtot] << "\n";

	fin.close();
	fout.close();
	return 0;
}