#include<fstream>
using namespace std;
int maxim, n, g, W[10003], pmax, i, j, G[5003], V[5003];
ifstream f("rucsac.in");
ofstream gg("rucsac.out");
int main(){
    f>>n>>g;
    for(i=1; i<=n; i++)
        f>>G[i]>>V[i];
    pmax=0;
    for(i=1; i<=n; i++){
        for(j=pmax; j>=0; j--){
            W[0]=1;
            if(W[j]!=0 && j+G[i]<=g){
                W[0]=0;
                if(W[j+G[i]]<W[j]+V[i])
                    W[j+G[i]]=W[j]+V[i];
                if(W[j+G[i]]>maxim)
                    maxim=W[j+G[i]];
            }
        }
        pmax+=G[i];
        if(pmax>g)
            pmax=g;
    }
    gg<<maxim<<"\n";
return 0;
}