#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

int N, G, pmax = 0;
vector<int> weight, profit, D;

void read(){

	in >> N >> G;
	weight.resize(N+1);
	profit.resize(N+1);
	D.resize(G+1);
	int w, p;

	for(int i = 1; i <= N; ++i){
		in >> w >> p;
		weight[i] = w;
		profit[i] = p;
	}
}


void Rucsac(){

	for(int i = 1; i <= N; ++i){
		for(int j = G - weight[i]; j >= 0; --j){
			if(D[j + weight[i]] < D[j] + profit[i]){
				D[j + weight[i]] = D[j] + profit[i];
				if(D[j + weight[i]] > pmax){
					pmax = D[j + weight[i]];
				}
			}
		}
	}
	out << pmax;
}


int main(){

	read();
	Rucsac();
	return 0;
}