# include <bits/stdc++.h>

#define nr 5010
#define gmax 10010

using namespace std;

int i,n,g,w[gmax],p[nr],prm[gmax],profmax,j;



int main()
{

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

    f>>n>>g;

    for(i=1;i<=n;++i)
        f>>w[i]>>p[i];

    for(i=1;i<=n;++i)
    {

        for(j=g-w[i];j>=0;j--)
        {


           if(prm[j+w[i]]<prm[j]+p[i])
           {


               prm[j+w[i]]=prm[j]+p[i];

               if(profmax<prm[j+w[i]])

               profmax=prm[j+w[i]];
           }

        }

    }

    fout<<profmax;

    return 0;



}