#include <cstdio>
#include <iostream>

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]={0};

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