#include <cstdio>

using namespace std;
#define N 1002
#define GMAX 100001
int w[N],p[N],n,G,pMax;
int max(int a,int b)
{
    return ((a<b)? b:a);
}
int pv[GMAX],v[GMAX];
FILE *f=freopen("rucsac.in","r",stdin),*g=freopen("rucsac.out","w",stdout);
int main()
{
    scanf("%d%d",&n,&G);
    int i,j;
    //cITIRE
    for(i=1;i<=n;++i)
    {
        scanf("%d%d",&w[i],&p[i]);
    }
    //Obtinem profit maxim pt D[i][j]-i elem la suma de greutate j
   for(i=0;i<n;++i)
        {for(j=0;j<=G;++j)
            if(w[i+1]>j)
                v[j]=pv[j];
            else {
                v[j]=max(pv[j],pv[j-w[i+1]]+p[i+1]);
            }
        for(j=0;j<=G;++j)//copiem pv in v
            pv[j]=v[j];
        }
        //solutia se afla la n obiecte cu greutate G
    printf("%d\n",v[G]);
}