#include <cstdio>
#define GMAX 10001
#define NMAX 5001

using namespace std;

long dp [GMAX];
long p [NMAX];
long g [NMAX];

void Read (long &N , long &G) {
	long i;
	scanf ("%ld%ld" , &N , &G);
	for (i = 1 ; i <= N ; i ++)
		scanf ("%ld%ld" , &g[i] , &p[i]);
}

void Solve (const long &N , const long &G) {
	long i , j , smax = 0 , max = -1;
	dp [0] = 1; 
	for (i = 1 ; i <= N ; i ++)  
		for (j = smax ; j >= 0 ; j --)
			if (dp [j] && j + g [i] <= G)
				if (dp [j + g [i]] < dp [j] + p [i]) {
					dp [j + g [i]] = dp [j] + p [i];
					if (j + g [i] > smax)
						smax = j + g [i]; 
					if (dp [j + g [i]] > max)
						max = dp [j + g [i]];
				}
	max --;
	printf ("%ld\n" , max);
}

int main () {
	long N , G;
	
	freopen ("rucsac.in" , "r" , stdin);
	freopen ("rucsac.out" , "w" , stdout);
	
	Read (N , G);
	Solve (N , G);
	return 0;
}