#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long 
#define ull unsigned long long 
#define nmax 5006
#define MOD 1999999973 
#define INF 2123456789
//#define fin cin 
//#define fout cout 

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

int n, G;
int v[nmax], g[nmax];
int dp[2  * nmax];

int main()
{
	int i, j, maxi;
	fin >> n >> G;
	for (i = 1; i <= n; i++)
		fin >> g[i] >> v[i];
	dp[0] = v[0];
	maxi = 0;
	for (i = 2; i <= n; i++)
		for (j = G - g[i]; j >= 0; j--)
			if (dp[j + g[i]] < dp[j] + v[i])
			{
				dp[j + g[i]] = dp[j] + v[i];
				maxi = max(maxi, dp[j + g[i]]);
			}
	fout << maxi << "\n";
	fin.close();
	fout.close();
	return 0;
}