#include <stdio.h>

int w[5000], p[5000], dp[10000];
int main(){
  FILE *fin, *fout;
  fin = fopen( "rucsac.in", "r" );
  fout = fopen( "rucsac.out", "w" );

  int n, i, g, max, j;
  fscanf( fin, "%d%d", &n, &g );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d%d", &w[i], &p[i] );
  max = 0;
  for ( i = 0; i < n; i++ ) {
    for ( j = g - w[i]; j >= 0; j-- ) {
      if ( dp[j + w[i]] < dp[j] + p[i] ) {
        dp[j + w[i]] = dp[j] + p[i];
        if ( dp[j + w[i]] > max )
          max = dp[j + w[i]];
      }
    }
  }
  fprintf( fout, "%d", max );
  fclose( fin );
  fclose( fout );
  return 0;
}