#include <iostream>
#include <fstream>

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

struct pachet{int g,v;}p[10005];
int N,G,k;

int valoare(int i, int G)
{
    if(G==0 || i==0) 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(k=1;k<=N;++k) fin>>p[k].g>>p[k].v;
    fout<<valoare(N,G);
    return 0;
}