#include <stdio.h>

int p[5001];
int g[5001];
int m[2][10001];

int main()
{
    FILE *f;
    int N,G,i,j,aux;

    f=fopen("rucsac.in","r");
    fscanf(f,"%d%d",&N,&G);
    for (i=1; i<=N; i++)
        fscanf(f,"%d%d",&g[i],&p[i]);
    fclose(f);

    aux=0;
    for (i=1; i<=N; i++)
    {
        for (j=0; j<=G; j++)
        {
            m[aux][j]=m[1-aux][j];
            if (j >= g[i] && (m[1-aux][j-g[i]]+p[i] >  m[aux][j]))
                m[aux][j]=m[1-aux][j-g[i]]+p[i];
        }
        aux=1-aux;
    }

    f=fopen("rucsac.out","w");
    fprintf(f,"%d",m[1-aux][G]);
    fclose(f);
}