#include <fstream>

using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
int a[3][10005],G,i,j,n,gr[10005],v[10005];
int main()
{
    int l=0;
    f>>n>>G;
    for(i=1;i<=n;i++)
    {
        f>>gr[i]>>v[i];
    }
    for(i=1;i<=n;i++, l=1-l)
        {for(j=0;j<=G;j++)
    {
        a[1-l][j]=a[l][j];
        if(gr[i]<=j) a[1-l][j]=max(a[1-l][j],a[l][j-gr[i]]+v[i]);

    }
}
    g<<a[l][G];
    return 0;
}