#include<stdio.h>

FILE *f=fopen("rucsac.in","r");
FILE *g=fopen("rucsac.out","w");

#define maxn 5001
#define maxg 10001

int greutate[maxn],profit[maxn],opt[maxg];
int i,j,n,gr,sol;
int main()
{
    fscanf(f,"%d %d",&n,&gr);
    for(i=1;i<=n;i++) fscanf(f,"%d %d",&greutate[i],&profit[i]);
    for (i=1;i<=n;i++)
    {
        for (j=gr-greutate[i];j>=0;j--)
        {
            if (opt[j+greutate[i]]<opt[j]+profit[i])
            {
                opt[j+greutate[i]]=opt[j]+profit[i];
                if (opt[j+greutate[i]]>sol) sol=opt[j+greutate[i]];
            }
        }
    }
    fprintf(g,"%d",sol);
    return 0;
}