#include <stdio.h>
#define FIN "rucsac.in"
#define FOUT "rucsac.out"
#define MAXW 10001
#define MAXC 5001

  int i,j,
      n,//number of objects
      g,//capacity of the knapsack
      w[ MAXW ], //weight
      c[ MAXC ]; //costs


int Profit(int n, int g) {

  int Cost[n+100][g+100]; 

  for(i = 1; i <= n; ++i) {

      for(j = 1; j <= g; ++j) {

          if(w[i] <= j) {

                  if(Cost[i - 1 ][ j ] < Cost[i - 1][j - w[i]] + c[ i ]) 
       
                      Cost[i][j] = Cost[i - 1][j - w[i]] + c[ i ];     

                  else 

                      Cost[i][j] = Cost[ i - 1][ j ];                  

           } else     Cost[i][j] = Cost[ i - 1][ j ];
      }
  } 

  return Cost[n][g];
}


int main() {

  freopen(FIN, "r", stdin);
  freopen(FOUT, "w", stdout);

  scanf("%d %d", &n, &g);

  for(i = 1; i <= n; i++) {
      scanf("%d", &w[ i ]);
      scanf("%d", &c[ i ]);
  }

  printf("%d", Profit(n,g));

 return(0);
}