#include <iostream>
#include <cstdio>
using namespace std;

int N,Gmax; int A[10010];//int A[5010][10010];
struct RUCSAC{int G,P;}v[5010];

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

    int i,j;

    scanf("%d%d", &N,&Gmax);
    for(i=1; i<=N; i++)
        scanf("%d%d", &v[i].G, &v[i].P);
/*
    for(i=1; i<=N; i++)
    {
        for(j=1; j<=Gmax; j++)
        {
            if(j<v[i].G) A[i][j]=A[i-1][j];
            else
                A[i][j]=max(A[i-1][j],v[i].P+A[i-1][j-v[i].G]);
        }
    }

    printf("%d\n",A[N][Gmax]);

    for(i=1; i<=N; i++)
    {
        for(j=1; j<=Gmax; j++) printf("%d ",A[i][j]);
        printf("%d\n");
    }

    i=N; int k=Gmax;

    while(i>0 && k>0)
    {
        if(A[i][k]!=A[i-1][k])
        {
            printf("%d ",i);
            k=k-v[i].G;
            i--;
        }
        else i--;
    }
*/
    A[0]=0; int PROFIT=0;

    for(i=1; i<=N; i++)
    {
        for(j=Gmax-v[i].G; j>=0; j--)
        {
            if(A[j+v[i].G]<A[j]+v[i].P) A[j+v[i].G]=A[j]+v[i].P;
            if(PROFIT<A[j+v[i].G]) PROFIT=A[j+v[i].G];
        }
    }
    printf("%d\n",PROFIT);

    //for(i=1; i<=Gmax; i++) printf("%d ",A[i]);

    return 0;
}