#include <stdio.h>
#include <stdlib.h>
#define MAXN 5000
#define MAXG 10000
  int dp[MAXG+1 ];
  int G[MAXN+1];
  int P[MAXN+1];

int max( int a, int b ) {
  return a > b ? a : b;
}
int main()
{
  FILE*fin;
  FILE*fout;
  fin = fopen("rucsac.in","r");
  fout = fopen("rucsac.out","w");

  int i,n,g,j,a,b;
  fscanf(fin,"%d%d",&n,&g);
  for(i = 0; i < n; i++){
    fscanf(fin,"%d%d",&G[i],&P[i]);
  }
  for ( i = 0; i < n; i++ )
    for ( j = g; j >= G[i]; j-- )
      dp[j] = max( dp[j], dp[j - G[i]] + P[i] );

  fprintf(fout,"%d",dp[g]);
  return 0;
}