#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int d[2][10001];
int n,g,linie_actuala,linie_opusa;
int gr[5001],pr[5001];
int main() 
{   fin>>n>>g;
	for(int i=1;i<=n;i++)
	{ fin>>gr[i]>>pr[i];
	}
	for(int i=1;i<=n;i++)
	 { linie_actuala=i%2;
	   linie_opusa=1-linie_actuala;
	 	for(int j=1;j<=g;j++)
	 {
 
 
	   d[linie_actuala][j]=d[linie_opusa][j];  
	  	if(gr[i]<=j)
	    {   d[linie_actuala][j]=max(d[linie_opusa][j],d[linie_opusa][j-gr[i]]+pr[i]);
 
 
 
	    }
 
	      }
	      }
 
 
	fout<<d[n%2][g];
 
 
	return 0;
}