#include <stdio.h>
#include <stdlib.h>
int max(int a,int b){
    if(a>b)
        return a;
    else
        return b;
}
int best[10001];
int main()
{
    FILE *fin,*fout;
    int n,g,s,x,i,y,max1,j;
    fin=fopen("rucsac.in","r");
    fout=fopen("rucsac.out","w");
    s=0;
    fscanf(fin,"%d%d",&n,&g);
    best[0]=1;
    for(i=0;i<n;i++){
        fscanf(fin,"%d%d",&x,&y);
        s+=x;
        for(j=s;j>=0;j--)
            if(best[j])
                if(j+x<=g)
                    best[j+x]=max(best[j+x],best[j]+y);
    }
    max1=0;
    for(i=0;i<=g;i++)
        if(best[i]>max1)
            max1=best[i];
    fprintf(fout,"%d",max1-1);
    return 0;
}