#include <bits/stdc++.h>
#define FIN "rucsac.in"
#define FOUT "rucsac.out"
#define MAXW 10000
#define MAXC 10000
#define MAXP 10000

using namespace std;


int main() {
  int n, g;
  int w[MAXW], c[MAXC], Cost[MAXP];

  ifstream fin(FIN);
  ofstream fout(FOUT);

  fin>>n>>g;

  for(int i = 1; i <= n; i++) {
      fin>>w[i];
      fin>>c[i]; 
  }

  for(int i = 0; i <= n; i++) {

      for(int j = g; j >= w[i]; j--) {

          Cost[ j ] = max(Cost[j], Cost[j - w[i]] + c[i]);
      }
  }



  fout<<Cost[g];


 return(0);
}