#include <fstream>
#include <algorithm>
#include <vector>

//std::vector< std::pair<int,int> >
int knapsack(std::vector< std::pair<int,int> > objects, int maxWeight)
{
    std::vector<int> dp(maxWeight+1,-1),aux(maxWeight+1);
    std::vector< std::pair<int,int> > solution;
    int solIndex=0;

    dp[ 0 ]=0;
    for(int i=0;i<(int)objects.size();i++)
    for(int j=maxWeight-objects[ i ].first;j>=0;j--)
    if(dp[j]!=-1 && dp[j] + objects[i].second > dp[ j + objects[i].first ])
    {
            dp[ j + objects[i].first ] = dp[j] + objects[i].second;
            aux[ j + objects[i].first ] = i;
            solIndex=(dp[solIndex] > dp[ j + objects[i].first ] ? solIndex : j + objects[i].first);
    }
    return dp[solIndex];
/*
    for(;solIndex;solIndex-=objects[ aux[solIndex] ].first)
        solution.push_back(objects[ aux[solIndex] ]);

    return solution;
*/}

int main()
{
    std::ifstream in("rucsac.in");

    std::vector< std::pair<int,int> > objects;
    int n,maxWeight;

    in>>n>>maxWeight;
    for(int i=0;i<n;i++)
    {
        std::pair<int,int> x;
        in>>x.first>>x.second;
        objects.push_back(x);
    }

    std::ofstream out("rucsac.out");

    /*
    int bestCost=0;
    for(auto obj: knapsack(objects,maxWeight))
        bestCost+=obj.second;
    out<<bestCost<<'\n';
    */
    out<<knapsack(objects,maxWeight)<<'\n';
    return 0;
}