#include <fstream>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	vector<int> W, P;
	ifstream infile; 
   	infile.open("rucsac.in");
	ofstream outfile;
	outfile.open("rucsac.out");

	int N, G, max = 0, val1, val2;
	infile >> N >> G;

	vector<int> Din(G + 1, 0);
     
	for (int i = 0; i < N; i ++) {
		infile >> val1 >> val2;
		W.push_back(val1);
		P.push_back(val2);
	}

	for (int i = 0; i <= G; i ++)
		for (int j = 0; j < N; j ++)
			if (i + W[j] <= G && Din[i + W[j]] < Din[i] + P[j]) {
				Din[i + W[j]] = Din[i] + P[j];
				if (Din[i + W[j]] > max)
					max = Din[i + W[j]];    
			}   
	
	outfile << max << endl;
	return 0;
}