#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_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];
    }
    //cazul 1-nu luam obiectul
    int profit1=dp_profit(idx-1, capacitate, objs);
    //cazul 2-luam obiectul
    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;
}