#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int n,gmax,maxx,cmax[5001],k;
struct ob
{
    int g,val;
} v[5005];
int compare(ob a,ob b)
{
    return (a.g<b.g || (a.g==b.g && a.val<b.val));
}
int main()
{
    f>>n>>gmax;
    for(int i=1; i<=n; i++)f>>v[i].g>>v[i].val;
    //sort(v+1,v+1+n,compare);
    cmax[0]=0;
    for(int i=1; i<=n; i++)

        for(int j=maxx; j>=0; j--)
        {
            if(cmax[v[i].g+j]<cmax[j]+v[i].val && (!j || cmax[j]) && v[i].g+j<=gmax)
            {
                cmax[v[i].g+j]=cmax[j]+v[i].val;
                if(j+v[i].g>maxx)maxx=j+v[i].g;
                }
        }
    int sol=0;
    for(int i=0; i<=gmax; i++) if(cmax[i]>sol)sol=cmax[i];
    g<<sol;
    /*for(int i=1;i<=n;i++)
        cout<<v[i].g<<" "<<v[i].val<<endl;*/
    return 0;
}