#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 5000, GMAX = 10000;

struct object{
	int weight, cost;
}v[NMAX + 1];

int dp[GMAX + 1];

int main(){

	int n, g;
	fin >> n >> g;

	for(int i = 1; i <= n; i++)
		fin >> v[i].weight >> v[i].cost;

	for(int i = n; i >= 1; i--)
		for(int w = g; w >= v[i].weight; w--)
			dp[w] = max(dp[w], dp[w - v[i].weight] + v[i].cost);
	
	int ans = 0;
	for(int w = 0; w <= g; w++)
		ans = max(ans, dp[w]);

	fout << ans << '\n';

	return 0;
}