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

int v[10001];

int main()
{
    int n,g,max,nr,p,c,i,MAXIM=0;
    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;
                    if(v[max+nr]>MAXIM)
                        MAXIM=v[max+nr];
                }
            }
        max=c;
    }
    fprintf(fo,"%d",MAXIM-1);
    fclose(fi);
    fclose(fo);
    return 0;
}