#include <iostream>
#include <fstream>

using namespace std;

int main(){
    int W[5001], P[5001], optim[10001], g, n;
    ifstream fin("rucsac.in"); ofstream fout("rucsac.out");
    fin>>n>>g;
    for(int i=1; i<=n; i++) fin>>W[i]>>P[i];
    optim[0]=0;
    int sol=0;
    for(int i=1; i<=n; i++)
        for(int j=g-W[i]; j>=0; j--){
            if(optim[j+W[i]]<optim[j]+P[i])
                {optim[j+W[i]]=optim[j]+P[i];
                 if(optim[j+W[i]]>sol) sol=optim[j+W[i]];};};
    fout<<sol;
    fin.close();
    fout.close();
    return 0;}