#include <bits/stdc++.h>

using namespace std;

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

int N,G,W[10001],P[10001],K[5001][10001];

int main()
{
	
	fin >> N >> G;
	
	for(int i=0;i<N;i++)
	    fin >> W[i] >> P[i];
	    
	for(int i=0;i<=N;i++)
	    for(int j=0;j<=G;j++)
	    {
	    	if(i==0 or j==0)
	    	    K[i][j]=0;
	    	else if(W[i-1]<=j)
	    	    K[i][j]=max(P[i-1]+K[i-1][j-W[i-1]],K[i-1][j]);
	    	else
	    	    K[i][j]=K[i-1][j];
		}
	
	fout << K[N][G];
	
	return 0;
	
}