#include <iostream>
#include <fstream>
#define DN 5005
#define DG 10005
using namespace std;

int n,g,dp[DN][DG],w[DN],p[DN];

int main()
{
	ifstream f("rucsac.in");
	ofstream out("rucsac.out");
	f>>n>>g;
	for(int i=1; i<=n; ++i) f>>w[i]>>p[i];
	for(int i=1; i<=n; ++i) for(int j=1; j<=g; ++j)
		if(j<=w[i]) dp[i][j]=dp[i-1][j];
		else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
	g<<dp[n][g];
	cout<<dp[n][g];
	return 0;
}