#include <stdio.h>
#include <stdlib.h>

int v[10001];

int main()
{
    int n,g,max,nr,p,c,i;
    FILE*fi,*fo;
    fi=fopen("rucsac.in","r");
    fo=fopen("rucsac.out","w");
    fscanf(fi,"%d%d",&n,&g);
    v[0]=1;
    max=0;
    for(i=0;i<n;i++)
        {
            fscanf(fi,"%d%d",&nr,&p);
            if(max+nr>g)
                max=g-nr;
            c=0;
            for(max;max>-1;max--)
                if(v[max]>0)
                    {
                        if(c==0)
                            c=max+nr;
                        if(v[max+nr]<v[max]+p)
                           v[max+nr]=v[max]+p;
                    }
            max=c;
        }
    fprintf(fo,"%d",v[max]-1);
    fclose(fi);
    fclose(fo);
    return 0;
}