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

#define MAXN 5001
#define MAXW 10001

using namespace std;

struct Object
{
    Object() :
        value(0),
        weight(0)
    {}
    
    Object(const int v, const int w) :
        value(v),
        weight(w)
    {}
    
    int value;
    int weight;
};

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

    void operator () (const Object& obj)
    {
        for (int w=obj.weight; w<=maxWeight; ++w)
        {
            valueTable[current][w] = max(valueTable[!current][w], valueTable[!current][w-obj.weight] + obj.value);
        }

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

private:

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

    int maxWeight;
    int current;
    int best;
    int* valueTable[2];
};

int main()
{
    int n, g, best=0;
    vector<Object> vObjects;
    
    fstream fin("rucsac.in", fstream::in);
    fstream fout("rucsac.out", fstream::out);
    
    fin >> n >> g;
    
    Solver solver(g);
    
    for (int i=0; i<n; ++i)
    {
        int v, w;
        fin >> w >> v;
        
        vObjects.push_back(Object(v,w));
        
        //cout << vObjects[i].value << " " << vObjects[i].weight << endl;
    }
    
    for_each (vObjects.begin(), vObjects.end(), solver);
    
    fout << solver.GetSolution() << endl;
    
    fin.close();
    fout.close();
    
    return 0;
}