#include <stdio.h>
#include <cstdio>
using namespace std;
///Considerăm un set de n obiecte, fiecarefiind caracterizatde o dimensiuned
///și de o valoare v, și un rucsacde capacitate C. Să se selecteze un subset
///de obiecte astfel incat dimensiunea totală a obiectelor selectate să fie mai
///mica decât C iar valoarea totală a obiectelorselectatesă fie maxim
int optim[4][10008];
FILE *f,*g;
int maximul(int a,int b)
{
    if(a>b)
        return a;
    else return b;
}
int greu[5005],val[5005];
void Dinamica(int n,int gt)
{
    int i,curent=2,precedent=1,j,aux;
    for(i=1;i<=n;i++,aux=curent,curent=precedent,precedent=aux)
        for(j=0;j<=gt;j++)
        {
            optim[curent][j]=optim[precedent][j];
            if(j>=greu[i])
                optim[curent][j]=maximul(optim[curent][j],optim[precedent][j-greu[i]]+val[i]);
        }
    fprintf(g,"%d",optim[precedent][gt]);
}
int main()
{
    f=fopen("rucsac.in","r");
    g=fopen("rucsac.out","w");
    int gr,n,i;
    fscanf(f,"%d %d",&n,&gr);
    for(i=1;i<=n;i++)
        fscanf(f,"%d %d",&greu[i],&val[i]);
    Dinamica(n,gr);
    fclose(f),fclose(g);
    return 0;
}
///* IMPLEMENTATION - EL DIG *///