using namespace std;
#include <fstream>
#include <algorithm>
#define NMAX 5005
#define GMAX 10005

FILE *f=fopen ("rucsac.in","r");
ofstream g ("rucsac.out");

int N,G;
int W[NMAX],P[NMAX];
int D[2][GMAX];

int main()
{
   int i,l=0,cw;

   fscanf(f,"%d%d",&N,&G);

   for(i=1; i<=N; i++)
    fscanf(f,"%d%d",&W[i],&P[i]);

   for(i=1; i<=N; i++, l=1-l)
    for(cw=1; cw<=G; cw++)
    {
        D[1-l][cw]=D[l][cw];

        if(W[i]<=cw)
        D[1-l][cw]=max(D[1-l][cw],D[l][cw-W[i]]+P[i]);
    }

    g<<D[l][G];


   return 0;
}