#include<stdio.h>

int w[5000], p[5000];
int Optim[10000];

int main() {

  FILE *fin, *fout;
  int n, g, i, j, sol;
  fin = fopen( "rucsac.in", "r" );

  fscanf( fin, "%d %d", &n, &g );

    for ( i = 0; i < n; i++ ) {
        fscanf( fin, "%d %d", &w[i], &p[i]);
    }

    Optim[0] = 0;
    sol = 0;

    for( i = 0; i < n; i++ )
        for( j = g - w[i]; j >= 0; j-- ) {
            if( Optim[j+w[i]] < Optim[j] + p[i] )
            {
                Optim[j+w[i]] = Optim[j] + p[i];
                if( Optim[j+w[i]] > sol)
                    sol = Optim[j+w[i]];
            }
        }
    fout = fopen( "rucsac.out", "w" );
    fprintf( fout, "%d", sol );
    fclose( fout );

    return 0;
}