#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int n, g1;

vector<int> c ,w;
int table[5000][10000];

int ks(int w1, int i)
{
    if(i+1 > n)
    {
        table[w1][i] = 0;
        return table[w1][i];
    }
    if(w1 < w[i])
    {
        if(table[w1][i+1] == NULL)
            table[w1][i+1] = ks(w1, i+1);
        return table[w1][i+1];
    }
    else
    {
        if(table[w1][i+1] == NULL)
            table[w1][i+1] = ks(w1,i+1);
        if(table[w1-w[i]][i+1] == NULL)
            table[w1-w[i]][i+1] = ks(w1-w[i],i+1);
        return max(table[w1][i+1], c[i]+table[w1-w[i]][i+1]);
    }
}

int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    f >> n >> g1;

    c.reserve(n);
    w.reserve(n);

    for(int i = 0; i < n; i++)
    {
        f >> w[i] >> c[i];
    }

    g << ks(g1,0);

    return 0;
}