#include <fstream>
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int dp[5005][10005];
int w[5005];
int v[5005];
int main() {
	int n, G;
	cin >> n >> G;
	for(int i = 1; i <= n; i++)
	{
		cin >> w[i] >> v[i];
	}
	for(int i = 1; i <= n; i++)
	{
		for(int g = 0; g <= G; g++)
		{
			dp[i][g] = dp[i - 1][g]; /// daca nu iau obiectul i
			if(w[i] <= g)
				dp[i][g] = max(dp[i][g], dp[i - 1][g - w[i]] + v[i]);
		}
	}
	int rez = 0;
	for(int i = 0; i <= G; i++)
		rez = max(rez, dp[n][i]);
	cout << rez << "\n";
	return 0;
}