#include <iostream>
#include <fstream>
#include <utility>
#include <vector>
#include <map>
using namespace std;
vector<pair<int, int> > Ob;
int nrO, G, a, b, pMax;

void RucsacNxG ();
void RucsacHash ();
void Read ();
int main()
{
    Read();
    //RucsacNxG();
    RucsacHash();
}
void RucsacHash()
{
    map<int, int> M, M2;
    M2.insert(make_pair(0, 0));
    for(int i = 1; i <= nrO; ++i)
    {
        if(Ob[i].first > G)
            continue;
        M.insert(make_pair(0, 0));
        map<int, int>::reverse_iterator rpos(M.upper_bound(G - Ob[i].first) );
        for(map<int, int>::reverse_iterator it = rpos; it != M.rend(); ++it) {
            int newG = it->first + Ob[i].first;
            if(newG <= G) {                                                     // Adauga un nou obiect
                int newProfit = it->second + Ob[i].second;
                int &s = M[newG];
                if(s == 0 || newProfit > s)
                    s = newProfit;
            }
        }
    }

    cout<<M.upper_bound(G-1)->second<<'\n';
}
void RucsacNxG()
{
    vector<int>D(G+1);
    for(int o=1; o<=nrO; ++o)
        for( int g=G; g>=0; --g)
            if(Ob[o].first <= g)
                D[g] = max(D[g], (D[g - Ob[o].first] + Ob[o].second) );

    for(int i=0; i<=G; ++i)
        pMax = max(pMax, D[i]);
    cout<<pMax<<'\n';
}
void Read ()
{
    freopen("rucsac.in", "rt", stdin);
    freopen("rucsac.out", "wt", stdout);
    scanf("%d%d", &nrO, &G);
    Ob.push_back(make_pair(0, 0));
    for(int i=1; i<=nrO; ++i){
        scanf("%d%d", &a, &b);
        Ob.push_back(make_pair(a, b));
    }
}