#include <fstream>

using namespace std;

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

int N, G, p[5000], g[5000];
int dp[3][10001];

void rucsac(){
	int i, j;
	for(int i=0; i<N; i++){
		for(int j=0; j<=G; j++)
            if (j < g[i])
                dp[(i+1)%2][j] = dp[i%2][j];
            else
                dp[(i+1)%2][j] = max(dp[i%2][j], p[i] + dp[i%2][j-g[i]]);
	}
}

/*void obiecte(){
	int i=N, j=G;
	while(dp[i][j] > 0){
		if (dp[i][j] == dp[i-1][j])
			i--;
		else{
			s[i-1] = 1;
			j = j-g[i-1];
			i--;
		}
	}
	fout << '\n';
	for(int i=0; i<N; i++)
        if(s[i])
            fout << i+1 << " ";
}*/

int main(){
    fin >> N >> G;
    for(int i=0; i<N; i++){
        fin >> g[i];
        fin >> p[i];
    }
    rucsac();
    fout << dp[N%2][G];
    //obiecte();
}