#include <cstdio>
#include <algorithm> 
#include <cstring>

using namespace std ;

#define MAXN 5010
#define MAXG 10010

int n, g ;
int w[MAXN], p[MAXN] ;
int d[MAXN][MAXG] ;
memset ( d[0], 0, sizeof(int)*(g+1) ) ;

int main () {
	int i, cw ;
	freopen ( "rucsac.in", "r", stdin ) ;
	scanf ( "%d %d\n", &n, &g ) ;
	for ( i=1; i<=n; ++i )
		scanf ( "%d %d\n", &w[i], &p[i] ) ;
	fclose ( stdin ) ;
	for ( i=1; i<=n; ++i )
		for ( cw=0; cw<=g; ++cw) {
			d[i][cw] = d[i-1][cw] ;
			if ( w[i] < cw ) 
				d[i][cw] = max ( d[i][cw], d[i-1][cw-w[i]] + p[i] ) ;
		}
	freopen ( "rucsac.out", "w", stdout ) ;
	printf ( "%d\n", d[n][g] ) ;
	fclose ( stdout ) ;
	return 0 ;
}