#include<cstdio>
using namespace std;
long long  d[4][10001];
long long w[5001],p[5001];
int main()
{
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    long long n,g;
    scanf("%lld%lld",&n,&g);
    int i,j;
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i],&p[i]);
    }
    for(i=1;i<=g;i++)
    {
        if(i<w[1])
            d[1][i]=0;
        else
            d[1][i]=p[1];
    }
    int nr1,nr2;
    for(i=2;i<=n;i++)
        {
          for(j=1;j<=g;j++)
            {
                nr1=d[1][j];
                if(j>w[i])
                    nr2=d[1][j-w[i]]+p[i];
                else
                    nr2=0;
                if(nr1>nr2)
                    d[2][j]=nr1;
                else
                    d[2][j]=nr2;
            }
           for(j=1;j<=g;j++)
           {
               d[1][j]=d[2][j];
           }
        }

    printf("%lld",d[1][g]);
    return 0;
}