#include <stdio.h>

#define MAX_N 5000
#define MAX_G 10000

int w[MAX_N], p[MAX_G], v[MAX_G + 1];

static inline int max( int a, int b ) {
  return a > b ? a : b;
}

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

  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] );
  fclose( fin );

  for ( i = 0; i < n; i++ )
    for ( j = g; j >= w[i]; j-- )
      v[j] = max( v[j], v[j - w[i]] + p[i] );

  fout = fopen( "rucsac.out", "w" );
  fprintf( fout, "%d\n", v[g] );
  fclose( fout );

  return 0;
}