#include <fstream>
#define GMAX 10010
#define NMAX 5010

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G;
int g[NMAX],c[NMAX],cmax[GMAX];

void citire();
void pd();

int main()
{
 citire();
 pd();
 fout<<cmax[G]<<'\n';
 return 0;
}
void citire()
{
 int i;
 fin>>n>>G;
 for (i=1;i<=n;i++)
      fin>>g[i]>>c[i];
}
void pd()
{
 int i,x;
 for (i=1;i<=n;i++)
    for (x=G;x>=1;x--)
         if (x>=g[i])
             if (cmax[x]<c[i]+cmax[x-g[i]])
                 cmax[x]=c[i]+cmax[x-g[i]];
}