#include <stdio.h>
#define MAXN 5000
#define MAXG 10000
int w[MAXN + 1];
int p[MAXN + 1];
int profit[MAXG + 1];
int max( int a , int b ) {
    return a < b ? b : a;
}
int main() {
    FILE *fin , *fout;
    int n , g , i , j , profitmax;
    fin = fopen( "rucsac1.in" , "r" );
    fscanf( fin , "%d%d" , &n , &g );
    for( i = 0 ; i < n ; i++ )
        fscanf( fin , "%d%d" , &w[i] , &p[i] );
    fclose( fin );
    for( i = 0 ; i < n ; i++ )
        for( j = g - w[i] ; j >= 0 ; j-- )
            profit[j + w[i]] = max( profit[j + w[i]] , profit[j] + p[i] );
    profitmax = 0;
    for( i = 0 ; i <= g ; i++ )
        profitmax = max( profit[i] , profitmax );
    fout = fopen( "rucsac1.out" , "w" );
    fprintf( fout , "%d\n" , profitmax );
    fclose( fout );
    return 0;
}