#include <iostream>
#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];
    }

    int profit1= 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,profit;
       fin>>greutate>>profit;
       t_object obj={greutate,profit};
       objs[i]=obj;
   }
   fout<<dp_profit(nr_elem,max_gr,objs);
   return 0;

}