#include <iostream>
#include <fstream>
#define nmax 5005
#define maxg  1000

using namespace std;

int n , gmax;
int c[nmax],g[nmax];
int Cmax[maxg],Uz[maxg][nmax];

void Citire()
{
    ifstream fin("rucsac.in");
    int i ;
    fin>>n>>gmax;
    for(i=1;i<=n;i++)
     fin>>g[i]>>c[i];
    //for(i=1;i<=n;i++)
     //fin>>c[i];

    fin.close();

}

void Rezolva()
{
    int s , k,i;
    for(s=1;s<=gmax;s++) Cmax[s]=-1;
    for(s=1;s<=gmax;s++)
     for(i=1;i<=n;i++)

        if(g[i]<=s && Cmax[s-g[i]]!=-1 && !Uz[s-g[i]][i])
       if(Cmax[s]<c[i]+Cmax[s-g[i]])
       {
           Cmax[s]=c[i]+Cmax[s-g[i]];
           for(k=1;k<=n;k++)
            Uz[s][k]=Uz[s-g[i]][k];
         Uz[s][i]=1;
       }


}



int main()
{
    Citire();
    Rezolva();

    ofstream fout("rucsac.out");
    fout<<Cmax[gmax];
    fout.close();
    return 0;
}