#include <iostream>
#include <fstream>

using namespace std;

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

#define NMax 5010
#define GMax 10010

int n, g;
int w[NMax], p[NMax];
int optim_n[GMax], optim_v[GMax];
int sol;

void init();
void rezolvare();

int main(){
	init();
	rezolvare();
}

void init(){
	fin >> n >> g;
	for(int i = 0; i < n; i++)
		fin >> w[i] >> p[i];
}

void rezolvare(){
	int i, j;
	for(i = 0; i < n; i++){
		for(j = 1; j <= g; j++){
			optim_n[j] = optim_v[j];
			if(j >= w[i] && optim_v[j - w[i]] + p[i] > optim_n[j]) optim_n[j] = optim_v[j - w[i]] + p[i];
			if(optim_n[j] > sol) sol = optim_n[j];
		}
		for(j = 1; j <= g; j++) optim_v[j] = optim_n[j];
	}
	fout << sol;
}