#include <fstream>

using namespace std;

int n,g,i,j,zr(0),un(1);
int w[10005], p[10005];
int a[2][10005];
int main ()
{   ios_base::sync_with_stdio(0);
    ifstream cin ("rucsac.in");
    ofstream cout("rucsac.out");
    
    cin >> n >> g;
    
    for (i=1; i<=n; i++)
    {
    cin >> w[i] >> p[i];	
	}
	
	for (i=1; i<=n; i++)
	{
	    for(j=1; j<=g; j++) if(w[i]>j) a[un][j]=a[zr][j];
	                        else a[un][j]=max(a[zr][j-w[i]]+p[i],a[zr][j]);
	swap(zr,un);
	}
	
	cout << max(a[zr][g],a[un][g]);
	
return 0;
}