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

int dp[10001];

int main(void)
{
    FILE *f,*g;
    int N,G;
    int w,p;
    int i,j;

    f=fopen("rucsac.in","r");
    if(f==NULL)
    {
        printf("eroare la deschiderea fisierului\n");
        exit(EXIT_FAILURE);
    }

    g=fopen("rucsac.out","w");
    if(g==NULL)
    {
        printf("eroare la deschiderea fisierului\n");
        fclose(f);
        exit(EXIT_FAILURE);
    }

    if(fscanf(f,"%d%d",&N,&G)!=2)
    {
        printf("eroare la citire\n");
        fclose(f);
        fclose(g);
        exit(EXIT_FAILURE);
    }

    for(i=0;i<N;i++)
    {
        if(fscanf(f,"%d%d",&w,&p)!=2)
        {
            printf("eroare la citire\n");
            fclose(f);
            fclose(g);
            exit(EXIT_FAILURE);
        }

        for(j=G;j>=w;j--)
            if(dp[j-w]+p>dp[j])
                dp[j]=dp[j-w]+p;
    }

    fprintf(g,"%d\n",dp[G]);

    if(fclose(f)!=0)
    {
        printf("eroare la inchiderea fisierului\n");
        exit(EXIT_FAILURE);
    }

    if(fclose(g)!=0)
    {
        printf("eroare la inchiderea fisierului\n");
        exit(EXIT_FAILURE);
    }

    return 0;
}