#include<fstream>
using namespace std;
int n, i, g, maxim, j;
int f[10001], m[10001];
pair<int, int> v[5001];
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int main(){
	fin>> n >> g;
	for(i = 1; i <= n; i++){
		fin>> v[i].first >> v[i].second;
	}
	f[0] = 1;
	for(i = 1; i <= n; i++){
		for(j = g; j >= 0; j--){
			if(f[j] == 1 && (j + v[i].first) <= g){
				f[j + v[i].first] = 1;
				if(m[j+v[i].first] < m[j] + v[i].second){
					m[j+v[i].first] = m[j] + v[i].second;
				}
			}
		}
	}
	for(i = 0; i <= g; i++){
		if(m[i] > maxim){
			maxim = m[i];
		}
	}
	fout<< maxim;
	return 0;
}