#include <stdio.h>
#define FIN "rucsac.in"
#define FOUT "rucsac.out"
#define MAXG 10001
#define MAXN 5001
#define MAXC 10001

int num_objects, 
    weight, 
    G[ MAXG ], 
    C[ MAXC ], 
    Cost[ MAXC ][ MAXC ];


void read();
void solve();

int main() {

    read(); 
    solve();

    return(0); 
};

void read() {

     int i;

     freopen(FIN, "r", stdin);

     scanf("%d %d", &num_objects, &weight);

     for(i = 1; i <= num_objects; i++) {

         scanf("%d %d", &G[ i ], &C[ i ]); 
     }          

     fclose( stdin ); 
};

void solve() {

     int i, 
         j;//for each weight ->from 1, to weight

     freopen(FOUT, "w", stdout);
 
     //for each object execute
     for(i = 1; i <= num_objects; i++) {

             //for each weight
             for(j = 1; j <= weight; j++) {

                     if(G[ i ] <= j) {

                               if( (C[ i ] + Cost[ i - 1 ][ j - G[ i ]]) > Cost[i - 1][ j ]) 

                                             Cost[ i ][ j ] = C[ i ] + Cost[ i - 1 ][ j - G[ i ]];

                                      else   

                                             Cost[ i ][ j ] = Cost[ i - 1 ][ j ];

                     } else {

                                             Cost[ i ][ j ] = Cost[ i - 1 ][ j ];
                            
                     }

             }   
     }

     printf("%d", Cost[ num_objects ][ weight ]);

     fclose( stdout );
}