#include <fstream>
using namespace std;

ifstream fin ("rucsac.in");
ofstream fout("rucsac.out");

int n,g,i,j,v[5005],w[5005],maxim;

void citire(){
    fin>>n>>g;
    for (i=1;i<=n;i++)
        fin>>w[i]>>v[i];
}

int rucsac(int n,int g){
    if (n==1 || g==0)
        return 0;
    if (w[n-1]>g)
        return rucsac(n-1,g);
    else
        return max(v[n-1]+rucsac(n-1,g-w[n-1]),rucsac(n-1,g));
}

int main(){
    citire();
    fout<<rucsac(n+1,g);
    fin.close();
    fout.close();
    return 0;
}