#include <cstdio>

using namespace std;

int v[10001];
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,g,i,j,max=0,l=0,m,p;
    scanf("%d%d",&n,&g);
    v[0]=1;
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&m,&p);
        for(j=l;j>=0;--j)
            if(v[j]!=0)
            {
                v[j+m]=v[j]+p;
                if(j==0)
                    v[j+m]--;
                if(j+m<=g&&v[j+m]>max)
                    max=v[j+m];
                if(j+m>l)
                    l=j+m;

            }
    }
    printf("%d",max);
    return 0;
}