#include <iostream>
#include <fstream>
using namespace std;

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

int G,n;
int p[5000],g[5000]; // in g retinem greutatile , in p profitul
int uz[5000][5000];
int d[5000];

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

void Rezolvare()
{

    int i,s,k;
    for(s=1;s<=G;s++) d[s]=-1;
    for(s=1;s<=G;s++)
     for(i=1;i<=n;i++)
      if(g[i]<=s && d[s-g[i]]!=-1 && !uz[s-g[i]][i])
       if(d[s]<p[i]+d[s-g[i]])
       {
           d[s]=p[i]+d[s-g[i]];
           for(k=1;k<=n;k++)
            uz[s][k]=uz[s-g[i]][k];
            uz[s][i]=1;
       }
       fout<<d[G];
}


int main()
{

     Citire();
     Rezolvare();

      return 0;
}