#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g;
int W[5001],P[5001];
int DP[1005][1005];

int main()
{
	fi>>n>>g;
	for(int i=1; i<=n; i++)
		fi>>W[i]>>P[i];
	for(int i=1; i<=n; i++)
		for(int j=1; j<=g;j++)
		{
			DP[i][j]=DP[i-1][j];
			if(W[i]<=j)
				DP[i][j]=max(DP[i-1][j],DP[i-1][j-W[i]]+P[i]);
		}
	fo<<DP[n][g];
	fi.close();
	fo.close();
	return 0;
}