#include <stdio.h>

int N, G, Pmax;
int W[5000], P[5000];
int D[5000][10000];

int main()
{
    int i,j;
    FILE *f=fopen("rucsac.in", "r");
    FILE *g=fopen("rucsac.out", "w");

    fscanf(f,"%d%d",&N,&G);
    for(i=1;i<=N;i++)
        fscanf(f,"%d%d",&W[i],&P[i]);

    for (i=0;i<=N;i++)
        D[i][0]=0;
     for (j=0;j<=G;j++)
        D[0][j]=0;

     for(i=1;i<=N;i++)
        for(j=0;j<=G;j++)
        {
            D[i][j]=D[i-1][j];
            if(W[i]<=j)
                if (D[i][j] < D[i-1][j-W[i]] + P[i])
                    D[i][j]=D[i-1][j-W[i]]+P[i];
        }

    Pmax = D[N][G];
    fprintf(g,"%d\n", Pmax);

    return 0;
}