#include <cstdio>

using namespace std;

inline int MAX(int a,int b)
{
    return ((a>b)?a:b);
}

int n,g,w[10005],p[10005],d[2][10005];

int main()
{
    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]);
    i=1;
    int j=0;
    for(int cw=1;cw<=g;cw++)
    {
        if(w[1]<=cw)
            d[j][cw]=p[i];
        else d[j][cw]=0;
    }
    ++j;
    ++i;
    while(i<=n)
    {
        {
        if(j==1)
        {
        for(int cw=1;cw<=g;cw++)
             d[j][cw]=MAX(d[j-1][cw],d[j-1][cw-w[i]]+p[i]);
             j=0;
             i++;
        }
        else
        {
         for(int cw=1;cw<=g;cw++)
            d[j][cw]=MAX(d[j+1][cw],d[j+1][cw-w[i]]+p[i]);
            j=1;
            i++;
        }
        }
    }
    if(j==1)
        printf("%d\n",d[0][g]);
    else printf("%d\n",d[1][g]);
    return 0;
}