#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#define NMAX 5001
#define GMAX 10001


using namespace std;

int Valoare[NMAX] , Greutati[NMAX] , Vect[GMAX];

int Nr_obiecte , Gr_maxima;
ifstream input("rucsac.in");
ofstream output("rucsac.out");



class Element
{
    double value;
    int index;
public:
    Element(const double & value , const int & index)
    {
        this->value = value;
        this->index = index;
    }
    double getValue()
    {
        return value;
    }
    int getIndex()
    {
        return index;
    }
    bool operator <(Element & val)
    {
        return this->value < val.getValue();
    }
};

int dinamica()
{
    int solutie = -1;
    for (int i = 0; i<GMAX; i++)
        Vect[i] = 0;

    for (int i = 0; i<Nr_obiecte; i++)
        for (int j = Gr_maxima - Greutati[i]; j>=0; j--)
            if (Vect[j + Greutati[i]] < Vect[j] + Valoare[i])
            {
                Vect[j + Greutati[i]] = Vect[j] + Valoare[i];
                if (solutie < Vect[j + Greutati[i]])
                    solutie = Vect[j + Greutati[i]];
            }
    return solutie;
}

void print(vector<Element> & elm)
{
    cout << "------\n";
    for (int i = 0; i<elm.size(); i++)
        cout << elm[i].getIndex() << " ";
    cout << "\n------\n";
}

double greedy_cu_heapuri()
{
    vector<Element> elemente;
    Element *elm;

    for (int i = 0; i<Nr_obiecte; i++)
    {
        elm = new Element(double(Valoare[i])/double(Greutati[i]) , i);
        elemente.push_back(*elm);
    }

    make_heap(elemente.begin(),elemente.end());

    double Solutie = 0.0;
    int Gr_copy = Gr_maxima;

    Element top = (*elemente.begin());
    pop_heap(elemente.begin(),elemente.end());
    elemente.pop_back();

    while (Gr_copy > Greutati[top.getIndex()])
    {
        Gr_copy -= Greutati[top.getIndex()];
        Solutie += Valoare[top.getIndex()];
        if (!elemente.empty())
        {
            top = (*elemente.begin());
            pop_heap(elemente.begin(),elemente.end());
            elemente.pop_back();
        }
        else
        {
            return Solutie;
        }
    }

    if (Gr_copy != 0)
    {
        Solutie += double(Valoare[top.getIndex()]) * double(Gr_copy) / double(Greutati[top.getIndex()]);
    }

    return Solutie;

}



void recursivitate(int k , int * & elemente , int & answer)
{
    if (k< Nr_obiecte)
    {
        int val_curenta = 0;
        int gr_curenta = 0 ;
        for (int i = 0; i<k; i++)
        {
            val_curenta += Valoare[elemente[i]];
            gr_curenta += Greutati[elemente[i]];
            if (i != k-1 && elemente[i] == elemente[k-1]) return;
        }

        if (answer < val_curenta) answer = val_curenta;
        for (int i = 0; i<Nr_obiecte; i++)
        {
            if (gr_curenta + Greutati[i] <= Gr_maxima)
            {
                elemente[k] = i;
                recursivitate(k+1 , elemente , answer);
            }
        }
    }
}

int backTracking()
{
    int * elemente = new int[Nr_obiecte + 1];

    int answer = -1;
    recursivitate(0 , elemente , answer);
    return answer;
}

int main()
{
    input >> Nr_obiecte >> Gr_maxima;
    for (int i = 0; i<Nr_obiecte; i++)
    {
        input >> Greutati[i] >> Valoare[i];
    }
    output << dinamica();
    input.close();
    output.close();
    return 0;
}