#include <bits/stdc++.h>

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
const int NMAX = 1e4 + 10;
int dp[NMAX];
int w[NMAX], c[NMAX];
int n, g;
int best;
signed main()
{
	fin >> n >> g;
	for (int i = 1; i <= n; i++)
	{
		fin >> w[i] >> c[i];
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = g - w[i]; j >= 0; j--)
		{
			dp[j + w[i]] = max(dp[j + w[i]], dp[j] + c[i]);
			best = max(best, dp[j + w[i]]);
		}
	}
	fout << best;
}