#include <iostream>
#include <fstream>
using namespace std;

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

int w[5000];
int p[5000];

int best(int i, int j)
{
    if(i == 0 || j == 0)
    {
        //cout << "i=" << i << endl;
        //cout << "j=" << j << endl;
        return 0;
    }
    if(j < w[i-1]) return best(i - 1, j);
    int a = best(i - 1, j);
    int b = best(i - 1, j - w[i-1]) + p[i-1];
    return (a > b ? a : b);
}

int main()
{
    int n, g;
    in >> n >> g;
    for(int i = 0; i < n; i++)
    {
        in >> w[i] >> p[i];
    }
    out << best(n, g);

    return 0;
}