#include <stdio.h>

int l1[ 10002 ], l2[ 10002 ];

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

    // Citire
    int N, G;
    fscanf( fin, "%d%d", &N, &G );

    // Setam profitul submultimii vide cu 1, urmand ca apoi sa-l scadem
    l2[ 0 ] = 1;
    
    // Programarea dinamica
    int i;
    for( i = 1; i <= N; i ++ ) {
        int W, P;
        fscanf( fin, "%d%d", &W, &P );

        // Copiem l2 in l1
        int j;
        for( j = 0; j <= G; j ++ ) {
            l1[ j ] = l2[ j ];
        }
        
        // Actualizam l2
        for( j = W; j <= G; j ++ ) {
            if( l1[ j - W ] + P > l1[ j ] ) {
                l2[ j ] = l1[ j - W ] + P;
            }
        }
    }
    
    // Gasire maxim
    int max = 0;
    for( i = 0; i <= G; i ++ ) {
        if( l2[ i ] > max ) {
            max = l2[ i ];
        }
    }

    fprintf( fout, "%d\n", max - 1 );

    fclose( fin );
    fclose( fout );
    return 0;
}