#include <fstream>
#define NMAX 5011
#define GMAX 10011
int optim[GMAX],g[NMAX],p[NMAX];
using namespace std;
int main(){
    int N,G,Sol,i,j;
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    in>>N>>G;
    for(i=1;i<=N;i++)
     in>>g[i]>>p[i];
    optim[0]=0;
    Sol=0;
    for(i=1;i<=N;i++)
     for(j=G-g[i];j>=0;j--)
      if(optim[j+g[i]]<optim[j]+p[i]){
       optim[j+g[i]]=optim[j]+p[i];
       if(optim[j+g[i]]>Sol) Sol=optim[j+g[i]];
      }
    out<<Sol<<"\n";
    in.close(); out.close();
    return 0;
}