#include <fstream>
#include <algorithm>

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

int main() 
{
    int solution[10005];
    int numberObjects;
    int maxWeight;
    int currentWeight;
    int currentProfit;
    int maximum = 0;

    in >> numberObjects >> maxWeight;

    /* Considering void solution set as valid */
    solution[0] = 1;

    for (int i = 0; i < numberObjects; i++) 
    {
        in >> currentWeight >> currentProfit;

        /* Increasing order would lead to updating the same solution multiple times */
        for (int weight = maxWeight; weight >= currentWeight; weight--) 
        {
            if (solution[weight - currentWeight] > 0)
            {
                solution[weight] = std::max(solution[weight - currentWeight] + currentProfit, solution[weight]);
            }
        }

        /* Older solutions (with weight < currentWeight) are kept updated, so we don't have to copy them */
    }

    for (int j = maxWeight; j >= 1; j--)
    {
        maximum = std::max(solution[j], maximum);
    }

    /* As the void solution has weight 1, we have to decrease the optimal one */
    out << maximum - 1;

    return 0;
}