#include <fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");
int w[5001],p[5001],d[10001],i,n,G,j;
int main ()
{
    f>>n>>G;
    for(i=1;i<=n;i++)
        f>>w[i]>>p[i];
    for(i=1;i<=n;i++)
        for(j=G;j>=w[i];j--)
            if(d[j-w[i]]+p[i]>d[j])
                d[j]=d[j-w[i]]+p[i];
    g<<d[G]<<" ";
}