#include <fstream>

using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
struct sdt
{
    int gr,pr;
}a[5003];
int s[10003];
int main()
{
    int n,g,gmax;
    in>>n>>g;
    for(int i=1;i<=n;i++)
    {
        in>>a[i].gr>>a[i].pr;
    }
    if(a[1].gr<=g)
    {
        gmax=a[1].gr;
        s[gmax]=a[1].pr;
    }
    else
        gmax=0;
    for(int i=2;i<=n;i++)
    {
        for(int j=gmax;j>=0;j--)
        {
            if(s[j]!=0)
                if(j+a[i].gr<=g)
                    s[j+a[i].gr]=max(s[j+a[i].gr],s[j]+a[i].pr);
        }
        if(gmax+a[i].gr<=g)
        {
            gmax+=a[i].gr;
        }
        else gmax=g;
    }
    out<<s[g];
    return 0;
}