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