#include <iostream>
#include <fstream>

#define in short int
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
in nr,greutate,greu[5001],prof[5001],ma[10001],mat[10001];
void citire()
{
  f>>nr>>greutate;
  for(in i=1;i<=nr;i++)f>>greu[i]>>prof[i];//greutati si profit

}
void afisare()
{
    for(int i=1;i<=greutate;i++)cout<<mat[i]<<" ";
    cout<<endl;
}
void dinamica ()
{
    mat[greu[1]]=prof[1];//am scris prima linie
    //afisare();
 for(in linie=2;linie<=nr;linie++)
 {
     for(in j=1;j<=greutate;j++)ma[j]=mat[j];
     if(prof[linie]>mat[greu[linie]])mat[greu[linie]]=prof[linie];

     for(in j=greu[linie]+1 ;j<=greutate ; j++ ){
        if((ma[j-greu[linie]]+prof[linie] > mat[j])&&(ma[j-greu[linie]]!=0))
            {
                mat[j]=ma[j-greu[linie]]+prof[linie];
        }
     }
    // afisare();

 }
    in MAX=0;
    for(in i=1;i<=greutate;i++)if(MAX<mat[i])MAX=mat[i];
    g<<MAX;
}

int main()
{
    citire();
    dinamica();
    return 0;
}