#include<fstream>
using namespace std;
int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    int j,i,g,n;
    int v[10005],w[5005],p[5005];
    in>>n>>g;
    for(i=1;i<=n;i++)
        in>>w[i]>>p[i];
    for(i=1;i<=n;i++)
        for(j=g-w[i];j>=0;j--)
            if(v[j]!=-1&&v[j]+p[i]>v[j+w[i]])
                v[j+w[i]]=v[j]+p[i];
    for(j=g;j>=0&&v[j]==-1;j--);
    out<<v[j]<<"\n";
    return 0;
}