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