#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout ("rucsac.out");

int n,g,w[5002],p[5002],d[2][10002];

int main ()
{
    fin>>n>>g;
    for(int i=1;i<=n;i++){
        fin>>w[i]>>p[i];
    }
    int l=0;
    for(int i=1;i<=n;i++){
          l=1-l;
          for(int j=1;j<=g;j++){
              d[l][j]=d[1-l][j];
              if(w[i]<= j)d[l][j]=max(d[l][j],d[1-l][j-w[i]]+p[i]);
            }
    }
    fout<<d[l][g];
    return 0;
}