#include <iostream>
#include<fstream>
using namespace std;

ifstream fin("rucsac.in");
ifstream fout("rucsac.out");

const int MAX_N = 5001;
const int MAX_G = 10000;

struct t_object
{
    int greutate;
    int profit;
};

int memo[MAX_N][MAX_G];

int dp_profit(int idx, int capacitate, t_object objs[])
{
    if(idx == 0)
    {
        return 0;
    }

    if(capacitate == 0)
    {
        return 0;
    }

    if(memo[idx][capacitate] != 0)
    {
        return memo[idx][capacitate];
    }

    if(objs[idx].greutate>capacitate)
    {
        memo[idx][capacitate] = dp_profit(idx-1, capacitate, objs);
        return memo[idx][capacitate];
    }

    int profit = dp_profit(idx-1, capacitate, objs);

    int new_capacitate = capacitate - objs[idx].greutate;
    int profit2 = objs[idx].profit + dp_profit(idx - 1, new_capacitate, objs);

    memo[idx][capacitate] = max(profit1, profit2);
    return memo[idx][capacitate];
}
int main()
{
    int nr_elem;
    int max_gr;

    t_object objs[MAX_N];

    fin >> nr_elem;
    fin >> max_gr;

    for(int i=1; i<= nr_elem; i++)
    {
        int greutate;
        int profit;

        fin>>greutate;
        fin>>profit;

        t_object obj = {greutate, profit};
        objs[i] = obj;
    }

    fout << dp_profit(nr_elem, max_gr, objs);
    return 0;
}