#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

struct suly{
	int s;
	int e;
};

bool contains(vector<int> indexes, int ind){
	for(int i : indexes){
		if(i == ind) return true;
	}
	return false;
}

int getmax(int* a, int n){
	int max = a[0];
	for(int i = 0; i < n; i++){
		if(a[i] > max) max = a[i];
	}
	
	return max;
}

void out(int *a, int n){
	for(int i = 0; i < n; i++){
		cout << a[i] << '\t';	
	}
	cout << '\n';
}

int main(){
	
	int g;
	int n;

	ifstream cin("rucsac.in");
	cin >> n >> g;
	suly s[n];
	for(int i = 0; i < n; i++){
		cin >> s[i].s >> s[i].e;
	}
	cin.close();
	
	int t[g+1];
	
	vector<int> indexes[g+1];
	
	for(int i = 0; i <= g; i++){t[i] = 0;}
	
	for(int i = 0; i < n; i++){
		if(t[s[i].s] < s[i].e){
			t[s[i].s] = s[i].e;
			indexes[s[i].s].clear();
			indexes[s[i].s].push_back(i);
		}
		
		for(int j = 0; j < g; j++){
			if(t[j] != 0 && j+s[i].s <= g && !contains(indexes[j], i) && t[j+s[i].s] < t[j] + s[i].e){
				t[j+s[i].s] = t[j] + s[i].e;
				indexes[j].clear();
				for(int ind : indexes[j]){
					indexes[j + s[i].s].push_back(ind);
				}
				indexes[j + s[i].s].push_back(i);
			}
		}
	//	out(t, g+1);
	}
	
	ofstream cout("rucsac.out");
	cout << getmax(t, g+1);
	cout.close();
}