#include <stdio.h>
#define NMAX 5000
/// Cristian Francu ajuta !

int W   [ NMAX + 1 ] ;
int P   [ NMAX + 1 ] ;
int mat [ 2 ] [ NMAX * 2 ] ;

int max (int a, int b ) {
  if ( a > b )
    return a ;
  return b ;
}

int main()
{
  FILE *fin, *fout ;

  fin = fopen ("rucsac.in", "r" ) ;
  fout = fopen ("rucsac.out", "w" ) ;

  int n, g, i, l, j ;

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

  for (i = 1 ; i <= n ; i++ ) {
    fscanf (fin, "%d%d", &W[i], &P[i] ) ;
  }

  l = 0 ;
  for (i = 1 ; i <= n ; i++ ) {
    for (j = 0 ; j <= g ; j++ ) {
      mat[1-l][j] = mat[l][j] ;

      if (W[i] <= j ) {
        mat[1-l][j] = max(mat[1-l][j], (mat[l][j-W[i]] + P[i]) ) ;
      }
    }
    l = 1 - l ;
  }
  fprintf (fout, "%d", mat[l][g] ) ;
  return 0;
}