#include <stdio.h>
#include <stdlib.h>
#define NMAX 5000
#define GMAX 10000

int gr[NMAX+1], val[NMAX+1];
int d[2][GMAX+1];

int main() {
    FILE *fin, *fout;
    int n, g, i, j, b;

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

    for( i = 1; i <= n; i++ ) {
      for( j = 0; j <= g; j++ ) {
        b = i & 1;
        d[b][j] = d[1-b][j];
        if( gr[i] <= j && d[1-b][j-gr[i]] + val[i] > d[b][j] )
          d[b][j] = d[1-b][j-gr[i]] + val[i];
      }
    }

    fout = fopen( "rucsac.out", "w" );
    fprintf( fout, "%d\n", d[n&1][g] );
    fclose( fout );
    return 0;
}