#include <cstdio>

using namespace std;

#define NMAX 5015
#define maxim(a,b) ((a>b)?(a):(b))

int W[NMAX],DP[2][2*NMAX],P[NMAX],N,G,Rez;

void Read()
{
    freopen("rucsac.in","r",stdin);
    int i,w,p;
    scanf("%d%d",&N,&G);
    for(i=1;i<=N;i++)
        scanf("%d%d",&W[i],&P[i]);
}

void TSFH()
{
    int i,j,l;
    for(i=1,l=1;l<=N;i=1-i,l++)
        for(j=0;j<=G;j++)
        {
            DP[i][j]=DP[1-i][j];

            if(W[l]<=j)
                DP[i][j]=maxim(DP[i][j],DP[1-i][j-W[l]]+P[l]);
        }

    Rez=DP[1-i][G];
}

void Print()
{
    freopen("rucsac.out","w",stdout);
    printf("%d\n",Rez);
}

int main()
{
    Read();
    TSFH();
    Print();
    return 0;
}