#include<stdio.h>

#define maxN 5005
#define maxG 10005

FILE*f=fopen("rucsac.in","r");
FILE*g=fopen("rucsac.out","w");

int N,G,i,j,best,maxobt;
int S[maxG];

struct obiect{
	int g;
	int v;
}A[maxN];

inline int min ( int a , int b ){
	return a <= b ? a : b;
}

inline int max ( int a , int b ){
	return a >= b ? a : b;
}

int main () {
	
	fscanf(f,"%d %d",&N,&G);
	
	for ( i = 1 ; i <= N ; ++i ){
		fscanf(f,"%d %d",&A[i].g,&A[i].v);
	}
	
	S[0] = 1;
	for ( i = 1 ; i <= N ; ++i ){
		for ( j = min(maxobt,G - A[i].g) ; j >= 0 ; --j ){
			if ( S[j] ){
				S[j+A[i].g] = max(S[j+A[i].g],S[j] + A[i].v);
				best = max(S[j+A[i].g],best);
				maxobt = max(maxobt,j+A[i].g);
			}
		}
	}
	--best;
	
	fprintf(g,"%d\n",best);
	
	fclose(f);
	fclose(g);
	
	return 0;
}