#include <iostream>
#include <fstream>

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

struct Pack{
    int g,v;
}p[10005];
int N,G;
int valoare(int i, int G){
    if(!G || !i) return 0;
    if(p[i].g>G) return valoare(i-1,G);
    return max(valoare(i-1,G),valoare(i-1,G-p[i].g)+p[i].v);
}
int main()
{
    fin>>N>>G;
    for(int k=1;k<=N;++k) fin>>p[k].g>>p[k].v;
    fout<<valoare(N,G);
    return 0;
}