#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 ) ;
	bool ok = true ;
	for ( i=1; i<=n; ++i, ok=!ok ) {
		for ( cw=0; cw<=g; ++cw) {
			d[ok][cw] = d[!ok][cw] ;
			if ( w[i] <= cw ) 
				d[ok][cw] = max ( d[!ok][cw], d[!ok][cw-w[i]] + p[i] ) ;
		}
	}
	freopen ( "rucsac.out", "w", stdout ) ;
	printf ( "%d\n", d[!ok][g] ) ;
	fclose ( stdout ) ;
	return 0 ;
}