#include <fstream>
#define LMAX 10005

using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int n, G;
int g[LMAX], c[LMAX];
int cmax[2][LMAX];
int lc=1, lp=0;

void citire();
void pd();

int main()
{
citire();
pd();
fout<<cmax[lp][G]<<'\n';
fin.close();
fout.close();
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=1;x<=G;x++)
              {
               cmax[lc][x]=cmax[lp][x];
               if (g[i]<=x&&cmax[lp][x-g[i]]+c[i]>cmax[lc][x])
                   cmax[lc][x]=cmax[lp][x-g[i]]+c[i];
              }
          lc=1-lc;
          lp=1-lp;
         }
    }