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

int maxim(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
void rucsac(FILE *fis,FILE *gis)
{
    int n=0,g=0,i=0,*w=NULL,*p=NULL,**a=NULL,l=0,j=0;
    fscanf(fis,"%d",&n);
    fscanf(fis,"%d",&g);
    w=(int*)malloc(n*sizeof(int));
    if(w==NULL)
    {
        perror("eroare la alocarea dinamic\n");
        exit(-1);
    }
    p=(int*)malloc(n*sizeof(int));
    if(p==NULL)
    {
        perror("eroare la alocarea dinamica\n");
        exit(-1);
    }
    for(i=0;i<n;i++)
    {
        fscanf(fis,"%d",&w[i]);
        fscanf(fis,"%d",&p[i]);
    }
    a=(int**)malloc(2*sizeof(int*));
    if(a==NULL)
    {
        perror("eroare la alocarea dinamic\n");
        exit(-1);
    }
    for(i=0;i<g;i++)
    {
        a[i]=(int*)malloc((g+1)*sizeof(int));
        if(a[i]==NULL)
        {
            perror("eroare la alocarea dinamica\n");
            for(j=0;j<i;j++)
                free(a[i]);
            exit(-1);
        }
    }
    for(i=0;i<2;i++)
    {
        for(j=0;j<=g;j++)
            a[i][j]=0;
    }
    for(i=1;i<=n;i++)
    {
        l=1-l;
        for(j=0;j<=g;j++)
        {
            a[1-l][j]=a[l][j];
            if(w[i]<=j)
            {   
                a[1-l][j]=maxim(a[1-l][j],a[l][j-w[i-1]]+p[i-1]);
            }
        }
    }
    fprintf(gis,"%d\n",a[1-l][g]);
    free(w);
    free(p);
    for(i=0;i<2;i++)
    {
        free(a[i]);
    }
    free(a);
}
int main(void)
{   
    FILE *fis=NULL,*gis=NULL;
    fis=fopen("rucsac.in","r");
    if(fis==NULL)
    {
        perror("eroare la deschidere fisier\n");
        exit(-1);
    }
    gis=fopen("rucsac.out","w");
    if(gis==NULL)
    {
        perror("eroare la deschidere fisier\n");
        exit(-1);
    }
    rucsac(fis,gis);
    fclose(fis);
    fclose(gis);

    return 0;
}