#include <fstream>
#include <bits/stdc++.h>

using namespace std;

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

unordered_map < string, int > mpp;
int N, G, W[5005], P[5005];

int value(int n, int remW)
{
    if(mpp[to_string(n) + "#" + to_string(remW)])
        return mpp[to_string(n) + "#" + to_string(remW)];
    if(remW == 0) return mpp[to_string(n) + "#" + to_string(remW)] = 0;
    if(n == N + 1) return mpp[to_string(n) + "#" + to_string(remW)] = 0;
    if(W[n] > remW) return mpp[to_string(n) + "#" + to_string(remW)] = value(n + 1, remW);
    return mpp[to_string(n) + "#" + to_string(remW)] = max(value(n + 1, remW), P[n] + value(n + 1, remW - W[n]));
}

int main()
{
    fin >> N >> G;
    for(int i = 1; i <= N; i++) 
    {
        fin >> W[i] >> P[i];
    }
    fout << value(1, G);
}