#include <fstream>
#define nmax 5005
#define gmax 10005
using namespace std;
ifstream fin ("rucsac.in");
ofstream fout("rucsac.out");

void citire();
void pd();
int i, g, lc=1, lp=0, n;
int gr[nmax], c[nmax];
int cmax[2][gmax];
int main()
{citire();
 pd();
 fout<<cmax[lp][g];
 return 0;
}
void citire()
{int i;
 fin>>n>>g;
 for(i=1; i<=n; i++)
     fin>>gr[i]>>c[i];
}
void pd()
{int i, x;
 for(i=1; i<=n; i++)
    {for(x=1; x<=g; x++)
         {cmax[lc][x]=cmax[lp][x];
          if(cmax[lp][x-gr[i]]+c[i]>cmax[lc][x]&&gr[i]<=x)
             cmax[lc][x]=cmax[lp][x-gr[i]]+c[i];
         }
     lp=1-lp; lc=1-lc;
    }
}