#include<cstdio>
#include<algorithm>

using namespace std;

const int NMAX = 5000+5;
const int GMAX = 10000+5;

void Read(),Solve(),Print();

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

int main()
{
    Read();
    Solve();
    Print();

    return 0;
}

void Read()
{
    int i;

    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    scanf("%d%d",&N,&G);

    for(i=1; i<=N; i++)
        scanf("%d%d",&W[i],&P[i]);
}

void Solve()
{
    int i,j;

    for(i=1; i<=N; i++)
        for(j=1; j<=G; j++)
            if(j-W[i]>=0) DP[i&1][j]=max(DP[(i-1)&1][j],DP[(i-1)&1][j-W[i]]+P[i]);
            else DP[i&1][j]=DP[(i-1)&1][j];
}

void Print()
{
    printf("%d\n",DP[N&1][G]);
}