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

using namespace std;

int n, g;
int w[10001], p[10001], Cost[10001];

int main() {

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

  fin>>n>>g;

  for(int i=1;i<=n; i++) {
      fin>>w[i];
      fin>>p[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]] + p[i]);
      }
  }


  fout<<Cost[g];

  return(0);
}