#include <stdio.h>
#include <stdlib.h>

#define MAXN 5000
#define MAXG 10000

int g[MAXN + 1], v[MAXN + 1];
int a[2][MAXG + 1];

int main() {
    int n, i, gtot, j, max, l;
    FILE *fin, *fout;

    fin = fopen( "rucsac.in", "r" );
    fscanf( fin, "%d%d", &n, &gtot );
    for( i = 1; i <= n; i++ )
        fscanf( fin, "%d%d", &g[i], &v[i] );
    fclose( fin );

    l = 1;
    for( i = 1; i <= n; i++ )
        for( j = 1; j <= gtot; j++ ) {
            l = i & 1;
            max = a[l][j];
            if( j - g[i] >= 0 && a[l][j - g[i]] + v[i] > max )
                max = a[l][j - g[i]] + v[i];
            a[1 - l][j] = max;
        }

    fout = fopen( "rucsac.out", "w" );
    fprintf( fout, "%d", a[1 - l][gtot] );
    fclose( fout );

    return 0;
}