#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>

#define MAXN 5001
#define MAXW 10001

using namespace std;

typedef unsigned int uint;

struct Object
{
    Object() :
        value(0),
        weight(0)
    {}
    
    Object(const uint v, const uint w) :
        value(v),
        weight(w)
    {}
    
    bool operator < (const Object& obj) const
    {
        return weight < obj.weight;
    }
    
    uint value;
    uint weight;
};

class Solver
{
public:
    Solver() :
        minWeight(0),
        maxWeight(MAXW),
        current(0),
        best(0)
    {
        InitValueTable();
    }
    
    Solver(const uint minW, const uint maxW) :
        minWeight(minW),
        maxWeight(maxW),
        current(0),
        best(0)
    {
        InitValueTable();
    }

    void operator () (const Object& obj)
    {
        for (uint w=obj.weight; w<=maxWeight; ++w)
        {
            uint candidate = valueTable[!current][w-obj.weight] + obj.value;
            
            if (candidate <= valueTable[!current][w])
            {
                memcpy(&valueTable[current][w], &valueTable[!current][w], sizeof(uint)*minWeight);
                w += (minWeight-1);
            }
            else
            {
                valueTable[current][w] = candidate;
            }
        }

        current = !current;
    }
    
    uint GetSolution() const
    {
        return valueTable[!current][maxWeight];
    }

private:

    void InitValueTable()
    {
        valueTable[0] = (uint*)calloc(maxWeight+1, sizeof(uint));
        valueTable[1] = (uint*)calloc(maxWeight+1, sizeof(uint));
    }

    uint minWeight;
    uint maxWeight;
    uint current;
    uint best;
    uint* valueTable[2];
};

int main()
{
    uint n, g, best=0;
    vector<Object> vObjects;
    
    fstream fin("rucsac.in", fstream::in);
    fstream fout("rucsac.out", fstream::out);
    
    fin >> n >> g;

    for (uint i=0; i<n; ++i)
    {
        uint v, w;
        fin >> w >> v;
        
        vObjects.push_back(Object(v,w));
        
        //cout << vObjects[i].value << " " << vObjects[i].weight << endl;
    }
    
    sort(vObjects.begin(), vObjects.end());
    
    Solver solver(vObjects[0].weight, g);
    
    for_each(vObjects.begin(), vObjects.end(), solver);
    
    fout << solver.GetSolution() << endl;
    
    fin.close();
    fout.close();
    
    return 0;
}