#include <fstream>
#define DIM 6000

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,i,j,G,maxi, w[6000], p[6000];
struct potae{
    int g,b;
} d[10005];
int main()
{
    fin>>n>>G;
    for(i=1;i<=n;i++){
        fin>>w[i]>>p[i];
        d[w[i]].g=1;
        d[w[i]].b=p[i];
    }
    for(i=1;i<=n;i++){
        for(j=G; j>=0; j--)
            if(d[j].g==1 && j+w[i]<=G  ){
                d[j+w[i]].g=1;
                d[j+w[i]].b=d[j].b+p[i];
                maxi=max(maxi, d[j+w[i]].b);
            }
    }
    fout<<maxi;
    return 0;
}