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

short 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=0; j<=g; ++j)
		if(j<w[i]) dp[i][j]=dp[i-1][j];
		else dp[i][j]=max((int)dp[i-1][j],dp[i-1][j-w[i]]+p[i]);
	out<<dp[n][g];
	//cout<<dp[n][g];
	return 0;
}