#include <stdio.h>
#define INF 2000000000
#define N_MAX 5000
#define G_MAX 10000
int w[ N_MAX ], p[ N_MAX ], d[ G_MAX + 1 ];

int main(){
    FILE *in = fopen ( "rucsac.in", "r" );
    int n, G, i, j;
    fscanf ( in, "%d%d", &n, &G );
    for ( i = 0; i < n; i++ )   fscanf ( in, "%d%d", &w[ i ], &p[ i ] );
    fclose ( in );

    for ( i = 0; i < n; i++ ){
        for ( j = G - w[ i ]; j >= 0; j-- ){
            if ( d[ j + w[ i ] ] < d[ j ] + p[ i ] ){
                d[ j + w[ i ] ] = d[ j ] + p[ i ];
            }
        }
    }

    FILE *out = fopen ( "rucsac.out", "w");
    fprintf ( out, "%d", d[ G ] );
    fclose ( out );
    return 0;
}