#include <fstream>
using namespace std;
int d[5001][10001], masa[5001], val[5001];
int main(){
  ifstream fin("rucsac.in");
  ofstream fout("rucsac.out");
    int n, G, maxg=-1;
    fin>>n>>G;
    for(int i=1;i<=n;i++)
      fin>>masa[i]>>val[i];
    for(int i=1;i<=n;i++){
      for(int g=masa[i];g<=G;g++)
        d[i][g]=max(d[i-1][g-masa[i]]+val[i], d[i-1][g]);

    }
    for(int i=1; i<=G; i++)
      if(maxg<d[n][i])
        maxg=d[n][i];
    fout<<maxg;
    return 0;
}