#include <cstdio>
using namespace std;
#define IN "rucsac.in"
#define OUT "rucsac.out"
int n , G;
int D[10002][10002];
struct element
{
int V,W;
}v[5003];
int maxim ( int a , int b )
{
if ( a > b )
return a;
else return b;
}
void Read()
{
int i;
scanf ( "%d%d" , &n , &G );
for ( i = 1 ; i <= n ; i ++ )
scanf ( "%d%d" , &v[i].W , &v[i].V );
}
void Solve()
{
int i , j;
for ( i = 1 ; i <= G ; i ++ )
D[0][i] = 0;
for ( i = 1 ; i <= n ; i ++ )
for ( j = 1 ; j <= G ; j ++ )
if ( j >= v[i].W )
{
D[i][j] = maxim(D[i-1][j] , D[i-1][j-v[i].W] + v[i].V );
}
else D[i][j] = 0;
printf ( "%d" , D[n][G] );
/* for ( i = 0 ; i <= n ; i ++ ){
for ( j = 1 ; j <= G ; j ++ )
printf ( "%d" , D[i][j] );
printf ( "\n");}*/
}
int main()
{
freopen ( IN , "r" , stdin );
freopen ( OUT , "w" , stdout );
Read();
Solve();
}