#include <fstream>
using namespace std;
int dp[5005];
int main(){
	int n, g, i, j, x, c, max_cost;
	ifstream fin( "rucsac.in" );
	ofstream fout( "rucsac.out" );
	fin >> n >> g;
	for( i = 0; i < n; i++ ){
		fin >> x >> c;
		for( j = g - x; j >= 0; j-- ){
			if( dp[j] + c > dp[j + x] ){
				dp[j + x] = dp[j] + c;
			}
		}
	}
	max_cost = 0;
	for( i = 0; i <= g; i++ ){
		max_cost = max( dp[i], max_cost );
	}
	fout << max_cost;
	return 0;
}