#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

int main(){
	ifstream in("rucsac.in");
	ofstream out("rucsac.out");
	int n,weight;
	int p[5005],w[5005];
	p[0] = w[0] =0;
	in >> n >> weight;
	for(int i = 1; i <= n; i++){
		in >> w[i] >> p[i];
	}
	int dp1[weight+10],dp2[weight+10];
	memset(dp1,0,sizeof(dp1));
	memset(dp2,0,sizeof(dp2));
	for(int i = 1; i <= weight; i++){
		if(w[1] <= i)
			dp2[i] = p[1];
	}

	for(int i=2 ; i <= n; i++){
		for(int j =1 ; j <= weight; j++){
			dp1[j] = dp2[j];
		}
		for(int j =1; j <= weight; j++){
			int elem = -1;
			if(j-w[i] >= 0){
				elem = p[i] + dp1[j-w[i]];
				// cout << i << " " << j << " " << elem << endl;
			}
			dp2[j] = max(dp1[j],elem);
		}
	
	}
	out << dp2[weight] << endl;
	return 0;
}