#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
using namespace std;
fstream fin("rucsac.in",ios::in),fout("rucsac.out",ios::out);
struct elemente{int w,p;};
elemente x[5002];
int pot[5002][10003];
int maxim=0,n,g,imax,gmax=-9;
bool cmp(elemente a,elemente b)
{
    if(a.w<b.w)
    {
        return 1;
    }
    if(a.w==b.w)
    {
        if(a.p>b.p)
        {
            return 1;
        }
    }
    return 0;
}
int main()
{
    int i,a,j,r,total=0,b;
    fin>>n>>g;
    for(i=1;i<=n;i++)
    {
        fin>>x[i].w>>x[i].p;
    }
    sort(x+1,x+n+1,cmp);

    for(i=1;i<=n;i++)
    {
        a=x[i].w;
        b=x[i].p;
        pot[i][a]=b;
        if((b>gmax)&&(a<=g))
        {
            gmax=b;
            imax=i;
        }
        for(j=1;j<=maxim;j++)
        {
            if(pot[i-1][j]!=0)
            {
                pot[i][j]=pot[i-1][j];
                pot[i][j+a]=pot[i-1][j]+b;
                if(pot[i][j]>gmax&&j<=g)
                {
                    gmax=pot[i][j];
                    imax=i;
                }
                if(pot[i][j+a]>gmax&&j+a<=g)
                {
                    gmax=pot[i][j+a];
                    imax=i;
                }
            }
        }
        maxim+=a;
    }
    fout<<gmax<<"\n";
    fout.close();
    fin.close();
    return 0;
}