#include <cstdio>
#include <algorithm>
#define NMAX 5000
#define GMAX 10000
using namespace std;

int n,G;
int Dynamic[NMAX][GMAX];
int Cost[NMAX];
int Weight[NMAX];
int Pmax;

inline void read(){

	freopen("rucsac.in","r",stdin);
  freopen("rucsac.out","w",stdout);
  scanf("%d%d",&n,&G);

  for(register int i = 1; i<= n; ++i)
  	scanf("%d%d",&Weight[i], &Cost[i]); 

}

inline void PD(){

	for(register int numberOfObj = 1; numberOfObj <= n; ++numberOfObj)
		for(register int currentWeight = 0; currentWeight <= G; ++currentWeight){

			Dynamic[numberOfObj][currentWeight] = Dynamic[numberOfObj-1][currentWeight];

			if(Weight[numberOfObj] <= currentWeight)
				Dynamic[numberOfObj][currentWeight] = max(Dynamic[numberOfObj][currentWeight],
				                                          Dynamic[numberOfObj-1][currentWeight - Weight[numberOfObj]]
				                                          + Cost[numberOfObj]);
		}  

Pmax = Dynamic[n][G];
printf("%d",Pmax);

}

int main(){

	read();
	PD();

return 0;
}