#include<stdio.h>
int g[5000],pret[5000],max[10000];
int main()
{
    FILE *fin,*fout;
    fin=fopen("rucsac.in","r");
    fout=fopen("rucsac.out","w");
    int n,G;
    fscanf(fin,"%d%d",&n,&G);
    int i;
    for(i=0;i<n;i++)
        fscanf(fin,"%d%d",&g[i],&pret[i]);
    max[0]=0;
    int j;
    int maxf=0;
    for(i=0;i<n;i++)
        for(j=G-g[i];j>=0;j--)
            if(max[j+g[i]]<max[j]+pret[i])
            {
                max[j+g[i]]=max[j]+pret[i];
                if(max[j+g[i]]>maxf)
                    maxf=max[j+g[i]];
            }
    fprintf(fout,"%d",maxf);
    return 0;
}