#include <iostream>
#include <fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
struct obiect{
    int g;
    int p;
};
int d[2][10003];
int main()
{   int n,w,i,j,l;
    obiect v[5003];
    in>>n>>w;
    for(i=1;i<=n;++i){
        in>>v[i].g>>v[i].p;
    }
//    for(i=1;i<=n;i++)
//        cout<<v[i].g<<v[i].p<<"\n";
    l=0;
    for(i=1;i<=n;++i,l=1-l){
        for(j=0;j<=w;++j){
            d[1-l][j]=d[l][j];
            if(v[i].g<=j)
                d[1-l][j]=max(d[1-l][j],d[l][j-v[i].g]+v[i].p);
        }
    }
    out<<d[l][w];
    return 0;
}