#include <iostream>
#include <fstream>


using namespace std;

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

int v[10000];
int w[10000];
int m[10001][5001];

int rucsac(int k,int g)
{
    if(m[k][g]!=0)
        return m[k][g];

    if(k==0)
        return 0;

    if(g >= w[k]){
        m[k][g] = max(rucsac(k-1,g-w[k]) + v[k],rucsac(k-1,g));
        return max(rucsac(k-1,g-w[k]) + v[k],rucsac(k-1,g));
    }
    else{
        m[k][g] = rucsac(k-1,g);
        return rucsac(k-1,g);
    }
}

int main()
{
    int n,g,i;
    fin >> n >> g;
    for(i=1;i<=n;++i)
        fin >> w[i] >> v[i];

    cout << rucsac(n,g);
    return 0;
}