#include <fstream>
#include <algorithm>
#define DMAX 5005

using namespace std;

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

int d[2][2*DMAX];
int p[DMAX],w[DMAX];
int n,sol,G;

void citire();
void rezolvare();
void afisare();

int main()
{
citire();
rezolvare();
afisare();
    return 0;
}

void citire()
{
int i;
fin>>n>>G;
for (i=1;i<=n;i++)
     fin>>w[i]>>p[i];
}

void rezolvare()
{
int i,g,lc=1,lprec=0,maxim;
for (i=1;i<=n;i++)
     {for (g=1;g<=G;g++)
          if (w[i]>g) d[lc][g]=d[lprec][g];
              else
              d[lc][g]=max(d[lprec][g-w[i]]+p[i],d[lprec][g]);
     lc=1-lc;
     lprec=1-lprec;
     }
sol=d[lprec][G];
}

void afisare()
{
fout<<sol<<'\n';
}