#include <fstream>
#include <iostream>
#include <algorithm>

std::ifstream f("rucsac.in");
std::ofstream g("rucsac.out");

int matrix[5001][10001];
int * a = new int[10001];
int * b = new int[10001];

int cost[5001];
int benefit[5001];
int N,G;

void read(){
	f >> N >> G;
	for(int i = 1; i <= N ;++i){
		f >> cost[i] >> benefit[i];
	}
}

void calculate(){
	for(int k = 1 ; k <= N ; ++k){
		for(int w = 1 ; w <= G ; ++w){
			if(cost[k] > w){
				b[w] = a[k - 1];
			}else{

				b[w] = std::max(a[w],a[w - cost[k]] + benefit[k]);
			}
		}
		int * tmp = a;
		a = b ;
		b = tmp;
	}

}

int main(){
	read();
	calculate();
	g<< std::max(a[G],b[G]);

	f.close();
	g.close();
	return 0;
	
}