///v2

#include<iostream>
#include<fstream>
using namespace std;
const int NMAX=5000, GMAX=10000;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int W[NMAX+1], P[NMAX+1];
int D[GMAX+1];
int main()
{
    int n,G,Pmax=0;
    fin>>n>>G;
    for(int i=1; i<=n; i++)
        fin>>W[i]>>P[i];
    int p=0,u=1;
    for(int i=1; i<=n; i++)
      for(int g=G-W[i];g>=0;g--)
      {
          int cw=g+W[i],
           cp=D[g]+P[i];
          if(D[cw]<cp)
          {
              D[cw]=cp;
              if(cp>Pmax) Pmax=cp;
          }
      }

    fout<<Pmax;

    fin.close();
    fout.close();
    return 0;
}