#include<cstdio>
int n,g,w[5002],d[3][10005],cw,p[5002],i;
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    scanf("%d%d",&n,&g);
    for(i=1;i<=n;i++)
        scanf("%d%d",&w[i],&p[i]);
    for(i=1;i<=n;i++)
    {
        for(cw=1;cw<=g;cw++)
        {
            d[2][cw]=d[1][cw];
            if(d[1][cw-w[i]]+p[i]>d[2][cw] && w[i]<=cw)
                d[2][cw]=d[1][cw-w[i]]+p[i];
        }
        for(cw=1;cw<=g;cw++)
            d[1][cw]=d[2][cw];
    }
    printf("%d",d[2][g]);
}