#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[2][MAXG] ;

void chestie  ( ) {
	int i ;
	for  ( i=1; i<=g; ++i ) 
		d[1][i] = d[2][i] ;
}
int main () {
	int i, cw ;
	freopen ( "rucsac.in", "r", stdin ) ;
	scanf ( "%d %d\n", &n, &g ) ;
	memset ( d[0], 0, sizeof(int)*(g+1) ) ;
	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] ) ;
		}
		chestie () ;
	}
	freopen ( "rucsac.out", "w", stdout ) ;
	printf ( "%d\n", d[n][g] ) ;
	fclose ( stdout ) ;
	return 0 ;
}