#include <fstream>

using namespace std;

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

const int max_n=5001;
const int max_g=10000;

struct t_obj
{
    int greutate;
    int profit;
};

int memo[max_n][max_g];

int dp_profit(int index, int cap, t_obj objs[])
{
    if(index==0)
    {
        return 0;
    }
    if(cap==0)
    {
        return 0;
    }
    if(memo[index][cap]!=0)
    {
        return memo[index][cap];
    }
    if(objs[index].greutate>cap)
    {
        memo[index][cap]= dp_profit(index-1, cap, objs);
        return memo[index][cap];
    }
    //nu bagam in rucsac
    int profit=dp_profit(index-1, cap, objs);
    //bagam in rucsac
    int new_cap= cap-objs[index].greutate;
    int profit2=objs[index].profit+dp_profit(index-1, new_cap, objs);
    memo[index][cap]=max(profit, profit2);
    return memo[index][cap];
}

int main()
{
    int nr_el;
    int max_gr;
    t_obj objs[max_n];
    fin>>nr_el;
    fin>>max_gr;
    for(int i=1; i<=nr_el; i++)
    {
        int gr;
        int profit;
        fin >> gr;
        fin>> profit;
        t_obj obj={gr, profit};
        objs[i]=obj;
    }
    fout<< dp_profit(nr_el, max_gr, objs);
    return 0;
}