// https://en.wikipedia.org/wiki/Knapsack_problem

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

int knapsack(std::vector< std::pair<int,int> > objects, int maxWeight)
/*
   Given a set of items, each with a weight and a value,
   returns the number of each item to include in a collection so that 
   the total weight is less than or equal to a given limit and the total value is as large as possible.
   (objects[index].first is weight and objects[index].second is value)
*/
{
    std::vector<int> dp(maxWeight+1,-1),aux(maxWeight+1,0);
    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 ] ? j + objects[i].first : solIndex);
    }
    return dp[solIndex];
}

int main()
{
    std::vector< std::pair<int,int> > objects;
    int n,maxWeight;

    std::ifstream in("rucsac.in");

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

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

    out<<knapsack(objects,maxWeight)<<'\n';

    out.close();
    return 0;
}