#include <cstdio>

int l1[10001], l2[10001], w[5001], p[5001];

inline int max( int a, int b ) {
    return a > b ? a : b;
}

int main () {
    FILE *f, *g;
    f = fopen( "rucsac.in", "r" );
    g = fopen( "rucsac.out", "w" );

    int n, G;

    fscanf( f, "%d%d", &n, &G );

    for( int i = 1 ; i <= n ; ++i )
        fscanf( f, "%d%d", &w[i], &p[i] );

    for( int j = 1 ; j <= G ; ++j )
        l1[j] = w[0] >= j ? p[0] : 0;

    for( int i = 1 ; i <= n ; ++i ) {
        for( int j = 1 ; j <= G ; ++j )
            if( j < w[i] )
                l2[j] = l1[j];
            else
                l2[j] = max( l1[j], l1[j - w[i]] + p[i] );
        for( int j = 1 ; j <= G ; ++j )
            l1[j] = l2[j];
    }

    fprintf( g, "%d\n", l1[G] );

    fclose( f );
    fclose( g );

    return 0;

}